\documentclass[a4paper,12pt]{book}
\usepackage[utf8]{inputenc}
\usepackage[pdftex]{graphicx}
\usepackage{verbatim}

\usepackage{algorithm}
\usepackage{algorithmic}
%094113727

\renewcommand{\contentsname}{Contenido}
\renewcommand{\partname}{Parte}
\renewcommand{\indexname}{Lista Alfabética}
\renewcommand{\appendixname}{Apéndice}
\renewcommand{\figurename}{Figura}
\renewcommand{\listfigurename}{Lista de Figuras}
\renewcommand{\tablename}{Tabla}
\renewcommand{\listtablename}{Lista de Tablas}
\renewcommand{\chaptername}{Capítulo}
\renewcommand{\partname}{Parte}
\renewcommand{\bibname}{Bibliografía}
\renewcommand{\listalgorithmname}{Lista de Algoritmos}

%%rename of the algorithmic tags
\renewcommand{\algorithmicend}{\textbf{fin}}
\renewcommand{\algorithmicif}{\textbf{si}}
\renewcommand{\algorithmicthen}{\textbf{entonces}}
\renewcommand{\algorithmicelse}{\textbf{de lo contrario}}
\renewcommand{\algorithmicelsif}{\algorithmicelse\ \algorithmicif}
\renewcommand{\algorithmicendif}{\algorithmicend}
\renewcommand{\algorithmicfor}{\textbf{para cada}}
\renewcommand{\algorithmicforall}{\textbf{para cada}}
\renewcommand{\algorithmicdo}{\textbf{hacer}}
\renewcommand{\algorithmicendfor}{\algorithmicend}
\renewcommand{\algorithmicendwhile}{\algorithmicend}
\renewcommand{\algorithmicwhile}{\textbf{mientras}}
\renewcommand{\algorithmicuntil}{\textbf{hasta que se cumpla}}
\renewcommand{\algorithmicrepeat}{\textbf{repetir}}


\floatname{algorithm}{Algoritmo}

\setcounter{tocdepth}{3}

\hyphenation{re-la-ti-va-men-te}
\hyphenation{a-cep-ta-bles}
\hyphenation{pro-ble-mas}
\hyphenation{ellas}
\hyphenation{do-cu-men-to}
\hyphenation{o-pe-ra-dor}
\hyphenation{me-ca-nis-mo}
\hyphenation{be-ne-fi-cio}
\hyphenation{in-di-vi-duos}
\hyphenation{con-cre-tas}
\hyphenation{do-mi-nan-tes}
\hyphenation{mo-de-la}
\hyphenation{par-ti-ci-pan-tes}
\hyphenation{al-go-rit-mos}
\hyphenation{re-fe-ren-cias}
\hyphenation{si-guien-te}
\hyphenation{he-rra-mien-tas}
\hyphenation{co-rres-pon-de}
\hyphenation{re-pre-sen-ta-do}
\hyphenation{cua-tro}
\hyphenation{o-pe-ra-cio-nes}
\hyphenation{bi-blio-te-ca}
\hyphenation{PNSGA}
%\oddsidemargin -1.0cm
%\headsep -2.4cm
\textwidth=14cm
%\textheight=26cm


\begin{document}
\title{Paralelismo Aplicado \\
     A Algoritmos Evolutivos\\
     Para Optimización Multiobjetivo}
\author{Alexis Rodríguez}
\date{2007}
\maketitle
\clearpage

\thispagestyle{empty}

\tableofcontents

\listofalgorithms


\chapter{Introducción}\label{chapter::intro}

\quote{
\footnotesize
\
{\it Whatever you do will be insignificant,
but it is very important that you do it.}

  - Mahatma Gandhi
}

\bigskip
\bigskip
\bigskip

El área de investigación operativa es una rama interdisciplinaria de las matemáticas que encuentra aplicaciones en lugares
 tan diversos como por ejemplo, la  maximización de ganancias en una empresa financiera, o la optimización de la velocidad de producción en una línea de 
ensamblaje. El problema genérico al que se enfrenta el área es presentado en la teoría como un conjunto de soluciones que se consideran factibles (según
el problema planteado), y una función objetivo que representa el criterio por el que se evalúa la 
optimalidad de cada posible solución.

Sin embargo en la práctica es difícil encontrar problemas de optimización con un solo objetivo, frecuentemente sucede que 
son varios los criterios involucrados en la búsqueda, (por ejemplo, los agentes de bolsa buscan maximizar el beneficio
y minimizar el riesgo a la hora de elegir un paquete de acciones sobre otro). En estas situaciones lo que se persigue 
es alcanzar un conjunto de soluciones que balanceen los criterios por los que buscamos, (en el caso del agente de bolsa,
 tal vez prefiera mantener un nivel relativamente alto de riesgo para obtener mayores ganancias). 
Es por eso importante que el tomador de decisiones defina la elección de las soluciones que sean mas adecuados según la priorización de objetivos,
 a partir de un abanico de soluciones óptimas que se le presentaran como resultado. Por supuesto
el ideal sería que existiera una solo solución que que optimice todas las funciones (le preste el máximo beneficio con riesgo cero, en el caso del agente de bolsa),
 pero ese caso es poco frecuente. De eso se tratan los problemas de Optimización con Múltiples Objetivos (MOP, por sus siglas en inglés), intentan brindar un conjunto
de soluciones que ponderan de manera diferente los múltiples objetivos del problema considerado. 

Actualmente existen dos grandes estrategias para resolver problemas de optimización de forma exacta: basadas en cálculo y enumerativas. 
Los métodos basados en cálculo han sido profundamente estudiados y a su vez se subdividen en dos clases primordiales: directos
e indirectos. Los métodos directos buscan el óptimo local ``moviéndose'' en el dominio (por ejemplo: utilizando como guía los valores de las derivadas parciales, 
este método es conocido como {\it hill climbing}). Los indirectos buscan el extremo local resolviendo un conjunto de ecuaciones (frecuentemente no lineales),
 obtenidas al igualar el gradiente de las ecuaciones a cero, esta técnica es la generalización multidimensional de la 
noción de cálculo elemental de los puntos extremos, que dada una función continua y no acotada, propone como forma de encontrar los máximos
restringir la búsqueda a aquellos puntos cuyas derivadas parciales se hacen cero. Estos dos métodos han sido mejorados,
extendidos y combinados, sin embargo, carecen de robustez. Muchos problemas de la vida real no son factibles de ser atacados por éstos
métodos, pues tienen como precondición que las funciones a optimizar sean continuas en el intervalo cerrado y acotado en el que buscan los óptimos. 
Las estrategias enumerativas tienen una base bastante mas sencilla: dentro de un espacio finito de búsqueda o en una discretización finita del
 espacio de búsqueda, el algoritmo evalúa todos los puntos y con esa información toma la decisión
 de cuales son los mejores resultados. A pesar de que la simplicidad de este método es muy atractiva los problemas reales comúnmente tienen un
espacio de búsqueda de gran tamaño, lo que descarta este método por falta de eficiencia computacional. 

Dadas las dificultades que presenta resolver el problema con precisión, un recurso bastante utilizado en computación es recurrir a técnicas
que alcanzan soluciones buenas rápidamente, pero que posiblemente no sean óptimas, conocidas como heurísticas. Como se estableció antes el resultado de los MOPs 
es un conjunto de soluciones, existen familias de heurísticas basadas en principios de la teoría de la evolución, que
operan sobre un conjunto de soluciones (conocido como población), que ``evolucionan'' a partir de soluciones tentativas aproximándose hacia las soluciones reales 
en un proceso iterativo. estas heurísticas se desarrollan en lo que se llama computación evolutiva. Como se presentará en los capítulos siguientes, 
estas técnicas brindan métodos de re\-so\-lu\-ción de una alta robustez, confiabilidad y un buen manejo de los recursos computacionales. 

El paralelismo es una  forma de resolver problemas cuando éstos exceden el poder de cómputo disponible, consiste en hacer que cooperen varios procesos en procesadores diferentes,
para resolver el problema. Debido a que en un algoritmo evolutivo las operaciones sobre la población no alteran otros entidades mas que las soluciones en sí mismas y además 
cada una de estas operaciones no necesita mas información que las funciones a optimizar, las técnicas de la computación evolutiva son fácilmente paralelizables 
aplicando {\it divide-and-conquer} o estrategias mas sofisticadas, como por ejemplo algunas inspiradas en la polinización de flores o la migración animal en una red de islas 
 \cite{cantu-paz95summary, 534133}. La aplicación del paralelismo a la computación evolutiva hace que se puedan enfrentar problemas reales de optimización con 
equipos de pequeño porte en términos de poder de cómputo.

La generalización de la aplicación de las técnicas de computación evolutiva a problemas con un solo objetivo a problemas con objetivos múltiples 
no es una tarea trivial. La extensión involucra un fuerte contenido matemático, haciéndose necesario volver a las bases de la investigación operativa 
para incorporar elementos de otras áreas \cite{zitzler98evolutionary}. 

%Las implantaciones de éstos algoritmos, a menudo son difíciles de encontrar, 
%cuanto mas aplicaciones de los mismos, sin embargo existen propuestas muy interesantes y prometedoras. Se podrán apreciar a lo largo de los ejemplos expuestos, la tendencia a la estandarización
%de éstas implementaciones, muchas veces en forma de {\it framework} o conjunto de esqueletos y no solamente en términos de implantación, sino que 
%adicionalmente, se pueden ver estandarizaciones en la forma de realizar {\it benchmarking} sobre los algoritmos. Todos éstos elementos nos llevan
%a la conclusión de que el área se está estabilizando, poniéndose al alcance de los usuarios.

El presente documento resume la investigación realizada sobre la resolución de problemas de optimización de objetivos múltiples a través
de algoritmos evolutivos y la aplicación del paralelismo a estas técnicas, se propone una vista en profundidad de las bases del área, tanto
desde el punto de vista de la investigación operativa, aprendizaje automático y la computación de alta rendimiento. Como producto de este trabajo
se detalla además la implementación de un conjunto de herramientas que servirán a los interesados en el área para investigar y utilizar estas metodologías
de manera sencilla y eficiente.


El resto del documento se organiza del modo que se describe a continuación: el capítulo \ref{chapter::mop} introduce formalmente el problema a resolver, que servirá
de marco teórico para el resto del documento, en el capítulo \ref{chapter::ae} se desarrollan conceptos vinculados a la computación evolutiva, el paralelismo y su aplicación a los
problemas multiobjetivos, en el capítulo \ref{chapter::pmoea} se referencian varias aplicaciones
de éstas técnicas a problemas reales y se introducen varios entornos de trabajo vinculados a los mismos, en el capítulo \ref{chapter::moe} se hace un
análisis exhaustivo de la propuesta e implementación de un {\it framework} para la investigación y desarrollo de soluciones en el área, en el capítulo \ref{chapter::results}
se presentan resultados de la aplicación de este {\it framework} a varios problemas estándar y finalmente en el capítulo \ref{chapter::final} se hacen conclusiones
respecto al trabajo realizado y se establecen varias líneas de trabajo futuro. 

%A lo largo de éste documento repasaremos de forma breve las bases que constituyen él área, se hará un paseo por la historia reciente, 
%se repasaran distintas propuestas de aplicación de estas técnicas y finalmente exhibiremos ejemplos de implementación, que
% nos servirán tanto de preámbulo como de justificación de varias decisiones de  diseño hacia la creación de un {\it framework} para aplicar
% el paralelismo a algoritmos evolutivos para resolver problemas de optimización con objetivos múltiples.

\chapter{Problemas de optimización multiobjetivo}\label{chapter::mop}

El problema de optimización multiobjetivo se resume a encontrar un vector de variables de decisión que satisfaga un conjunto de restricciones y
optimice una función vectorial, cuyos elementos representan las funciones objetivo que
conforman la descripción matemática del criterio de eficacia. Las funciones objetivo usualmente entran en conflicto
unas con otras, entonces, el término {\it optimizar} significa encontrar la solución que dará valores
aceptables a los objetivos, de acuerdo a criterios especificados por el tomador de decisiones.
A continuación se formalizarán estos conceptos de forma de dar una vista profunda a la teoría que nos servirá de cimientos para el
resto de los capítulos.

\section{Definiciones}


\paragraph{Variables de decisión}

Se trata de un vector que representa los diferentes elementos de los que se tiene control en un problema
de optimización, esas cantidades se denotan:
\begin{center}
$   \bar{x}
    = \left[
        \begin{array}{lcr}
            x_1,
            x_2,
            \cdots,
            x_n
        \end{array}
    \right] ^{T}$
\end{center}

\paragraph{Restricciones}

Se entiende por restricciones a condiciones que deberán cumplir las variables para ser tomadas
como factibles. Las restricciones se pueden plantear canónicamente en forma de inecuaciones del estilo:

\begin{eqnarray*}
g_i(\bar{x}) & \geq 0 & i = 1, \dots, m \\
h_i(\bar{x}) & \leq 0 & i = 1, \dots, p \\
\end{eqnarray*}

Es importante tomar en cuenta que la cantidad de igualdades debe de ser menor a la cantidad de variables de decisión, en caso
contrario el problema estaría sobre determinado.

\paragraph{Funciones objetivo}

Es el vector que contiene al conjunto de funciones que se quiere optimizar $f_1(\bar{x}),f_2(\bar{x}),\dots,f_k(\bar{x})$.

\begin{center}

    $
    \bar{f}(\bar{x}):\Re^n \rightarrow \Re^k$ y $\bar{f}(\bar{x}) = \left[
          \begin{array}{lcr}
            f_1(\bar{x}) \\
            f_2(\bar{x}) \\
            \vdots       \\
            f_k(\bar{x})
           \end{array}
         \right]
    $

\end{center}

Las definiciones previas permiten plantear el MOP formalmente, de la siguiente manera.

\begin{center}
Encontrar un vector
 $ {x}^{*}
    =   \left[
            \begin{array}{lcr}
                {x_1}^{*},
                {x_2}^{*},
                \cdots,
                {x_n}^{*}
            \end{array}
        \right]^{T}$  que cumpla
\end{center}

\begin{eqnarray*}
g_i({x}^{*}) & \geq 0 & i = 1, \dots, m \\
h_i({x}^{*}) & \leq 0 & i = 1, \dots, p \\
\end{eqnarray*}

\begin{center}
y optimice el vector función
$\bar{f}({x}^{*}) = {\left[
          \begin{array}{lcr}
            f_1({x}^{*}),
            f_2({x}^{*}),
            \cdots,
            f_k({x}^{*})
           \end{array}
         \right]}^{T}
$
\end{center}



Se le llama región de factibilidad (se denota $\Omega$), al espacio que satisface las restricciones, siendo cualquier punto
  $f(x) \backslash x \in \Omega$ una solución factible.


Es importante notar que las funciones no tienen porque coincidir en sus puntos óptimos de forma que un punto puede optimizar alguna
de las funciones pero no a otras. Dada esta situación el óptimo del problema entendido como el punto que optimiza a todas las funciones 
(también conocido como vector ideal), no existe. 

\paragraph{Optimalidad de Pareto}

Vilfredo Pareto \footnote{15 de julio de 1848 - 19 de agosto de 1923} realizó importantes contribuciones al estudio
de la economía (y de la sociología), especialmente en el campo de la distribución de la riqueza y el
análisis de las elecciones individuales. Contribuyó en diferentes áreas de la microeconomía, es el padre del concepto
de curva de indiferencia y además aportó un nuevo punto de vista a la definición de valor óptimo de un problema,
cuando varios criterios están involucrados. Las siguientes definiciones fueron extraídas del artículo de Van Veldhuizen escrito en el año 2000
\cite{state_of_the_art_2000}.

\paragraph{Dominación de Pareto}
Dado un vector $\bar{u}=(u_1, \dots, u_k)$ se dice que domina a $\bar{v}=(v_1,\dots, v_k)$ si y solo si
$\forall i \in \{ 1,\dots,k \}$ $u_i \leq v_i$ y $\exists i$ $\in$ $i \in \{1,\dots,k\}$ $\backslash$ $u_i < v_i$.
La relación de dominación se denota $\prec$.

\paragraph{Óptimo de Pareto}

Un punto $x^{*} \in \Omega$ es óptimo de Pareto si
$ \forall x \in \Omega$ $ f_i(x) = f_i(x^{*})$ con $i = 1,\dots,k$ 
o existe al menos un $i$ para el que $ f_i(x) > f_i(x^{*}) $.


Es clave ver que en realidad, cuando los óptimos de los objetivos no coinciden se tiene un conjunto de puntos
 óptimos de Pareto.


\paragraph{Conjunto Óptimo de Pareto}
Dado un MOP, el conjunto óptimo de Pareto ($P^*$) se define como:

$$P^{*}:=\{ x \in \Omega \backslash \not\exists x^{\prime} \in \Omega \backslash \bar{f}(x^{\prime}) \prec \bar{f}(x) \} $$

El Conjunto Óptimo de Pareto refiere al dominio, el codominio de esos puntos respecto al vector función del problema es el 
Frente de Pareto que se define a continuación.

\paragraph{Frente de Pareto} 
Dado un MOP y un Conjunto Óptimo de Pareto $P^*$, se define el Frente de Pareto como:

$$PF^{*}:=\{\vec{u} = F(x) = (f_1(x), \cdots, f_k(x)) \backslash x \in P^{*}\}$$

El conjunto de puntos óptimos según el criterio de Pareto se encontrará en los bordes de la
región de factibilidad o en puntos tangenciales de las curvas objetivo, no existiendo en la mayoría de los casos términos analíticos sencillos
para describir una expresión que represente ese conjunto de puntos. 

\section{Métodos de resolución}

Como se estableció en la introducción, actualmente existen tres grandes estrategias para resolver los problemas de optimización
\ y búsqueda: enumerativas, deterministas y estocásticas cite{vanveldhuizen99amultiobjective}. A pesar de que las técnicas enumerativas
son también deterministas se clasificarán diferente puesto que no suponen el uso de ninguna heurística.

\subsection{Enumerativas} 
Las estrategias enumerativas son quizás las mas simples, dentro de un espacio de búsqueda finito cada posible solución
es evaluada. Es sencillo observar que estas técnicas no son eficientes en la medida que los espacios de búsqueda sean grandes. Existen
refinamientos que permiten limitar el espacio de búsqueda con el objetivo de alcanzar soluciones suficientemente buenas en tiempos aceptables, se logran
a través de la introducción de conocimiento respecto al problema en particular.

\subsection{Deterministas}
Dentro de esta clasificación se encuentran las técnicas que como resultado obtienen el frente de Pareto, en un tiempo finito (siempre y cuando el problema
respete ciertas premisas). A continuación algunos ejemplos de éstas técnicas.

\paragraph{Basados en cálculo} 
Se trata de determinar analíticamente la solución utilizando la información de las funciones objetivo, una forma de aplicación de estos métodos es resolver la
ecuación que iguala los gradientes de la función a cero.

\paragraph{Algoritmos Codiciosos}
Conocidos también como {\it Greedy} por su nombre en inglés, basan su búsqueda en ``navegar'' el espacio direccionándose en base a condiciones
locales al punto o región que se está analizando al momento. Tienen como premisa que las soluciones subóptimas son siempre parte de la solución óptima global
al problema.

\paragraph{Hill Climbing} La ``navegación'' en este caso se rige por la pendiente, {\it Hill Climbing} toma siempre el camino en el cual la pendiente es 
más pronunciada. Ésta técnica tanto como la anterior toman decisiones que son irrevocables, es decir al tomar una decisión sobre la siguiente región a analizar
no guardan ninguna información sobre la misma por lo que no pueden volver a un estado anterior, ambas repetidamente expanden sus opciones a partir de una región y
toman el camino ``más prometedor''.

\paragraph{Backtracking} Es una técnica utiliza principalmente para bús\-que\-da en grafos, consiste en analizar cada región expandir las regiones vinculadas
y analizar cada una de ellas, tomando la mas prometedora según algún criterio, en caso de que se llegue a una situación en que se compruebe que se tomó una 
mala decisión estas técnicas tienen la capacidad de volver al estado anterior.

Las técnicas deterministas son aplicadas exitosamente a un largo conjunto de problemas \cite{vanveldhuizen99amultiobjective}. Sin embargo muchos
 problemas de optimización multiobjetivo tienen características que hacen que las técnicas deterministas sean poco efectivas. 
En efecto los MOPs  frecuentemente tienen muchas dimensiones, con espacios de bús\-que\-da muy grandes, discontinuos y multimodales. Problemas que 
exhiben una o mas de estas características se les llama irregulares, la aplicación de técnicas deterministas a problemas de este tipo es impracticable
ya sea por eficiencia o por no cumplir con las premisas de las mismas. 

\subsection{Estocásticas}
Las técnicas de búsqueda y optimización estocásticas son una aproximación alternativa a la resolución de problemas irregulares. Estos métodos
exigen que se pueda determinar que una solución es mejor que otra, es decir que exista una función que determine cuan adaptada es la solución al
problema, esta función se conoce como {\it fitness}. Las técnicas que se clasifican como estocásticas son heurísticas porque encuentran
 una buena solución pero no pueden garantizar que se trate de la solución óptima. 

\paragraph{Búsqueda Aleatoria}
También conocida como {\it Random Walk}, consiste simplemente en evaluar un conjunto aleatorio de soluciones, al analizar una región
seleccionan aleatoriamente cual será la siguiente región que se evaluará. Es ineficiente de manera similar a las técnicas Enumerativas, 
debido a las mismas razones y es de esperar que tengan rendimientos también similares.

\paragraph{Simulated Annealing}
Su nombre proviene de una técnica utilizada en la metalúrgica llamada recocido de metales ({\it Annealing} en inglés), es un proceso de
 reducción de las tensiones internas de un material e incremento de su fuerza y ductilidad al calentarlo, mantener la temperatura y 
reducir lentamente la misma hasta que enfríe. Análogamente al comportamiento de los átomos durante el proceso esta técnica {\it Simulated Annealing} realiza la búsqueda 
pasando a otro estado en cierta dirección seleccionada pro\-ba\-bi\-lís\-ti\-ca\-men\-te de forma que decisiones que produjeron en el pasado una mejora, tienen
mayor probabilidad que una que no lo hizo \cite{kirkpatrick83optimization}. La probabilidad de que se seleccione un movimiento decrece exponencialmente en
el tiempo o en la medida que empeore el estado del algoritmo.

\paragraph{Monte Carlo}
Utilizan Búsqueda Aleatoria, tomando varias muestras y reteniendo las mejores soluciones y sus variables de decisión como comparador,
para concentrar la búsqueda en áreas prometedoras.

\section{Resumen}
En este capítulo se presenta el MOP desde el punto de vista matemático y se plantean distintas alternativas para la resolución del mismo.
En el capítulo siguiente se presenta la computación evolutiva que es una técnica estocástica para resolver MOPs basada en la simulación
del proceso natural de evolución.
 
\chapter{Computación Evolutiva}\label{chapter::ae}

Desde la década de 1970 investigadores de distintas partes de los Estados Unidos y Europa,  manejaron independientemente la idea
de emular los mecanismos de la evolución biológica para desarrollar algoritmos para problemas de adaptación y optimización.
A través de la evolución surgen en la naturaleza varias estructuras óptimas como la forma de las alas de los pájaros o la estructura de
ramificaciones de las venas en el cuerpo humano. La idea de utilizar el mecanismo subyacente para la resolución de problemas de 
optimización ha motivado una cantidad considerable de investigación, resultando en muchas aproximaciones que han demostrado su
efectividad y robustez en una variedad de aplicaciones \cite{ck-evolutionary, whitley01overview, Rechenberg_1973}.

La computación evolutiva utiliza modelos del proceso de evolución como base en el diseño e implementación de sistemas de resolución
de problemas de optimización y adaptación. Existe variedad dentro de los modelos computacionales que se han propuesto y estudiado,
pero todos ellos serán referidos como algoritmos evolutivos. Todos comparten como concepto base la simulación de la evolución
de estructuras individuales vía procesos de selección y reproducción. Estos procesos dependen de la percepción de adaptabilidad
({\it fitness}) de las estructuras individuales dentro del entorno.

\section{¿Qué es un algoritmo evolutivo?}

Los Algoritmos Evolutivos (EA por sus siglas en inglés) mantienen un conjunto de individuos que evoluciona de acuerdo a reglas de selección y 
otros operadores, como la recombinación y mutación. Cada uno de los individuos en el conjunto (conocido como po\-bla\-ción) recibe una
medida de su adaptabilidad al entorno. La selección favorece a los individuos que presentan una mayor adaptación, manteniendo
las características que los destacan a lo largo de las generaciones, alimentando de esa forma la explotación de esas características. 
La recombinación y la mutación alteran a los individuos más adaptados dándole al algoritmo la capacidad de exploración de nuevas características
en los individuos.
%%@todo hablar de las codificaciones.
%, es importante notar que los individuos sobre los que trabaja el EA no son siempre las soluciones del problema de
%optimización, el EA puede operar sobre representaciones de esas soluciones codificándolas con el objetivo de aprovechar mejor los
%mecanismos del EA.

\begin{figure}[h]
\centering
\includegraphics[scale=0.35]{images/AE-Diagram.png}
\caption{Flujo de ejecución de un algoritmo evolutivo.}\label{ae:flow}
\end{figure}




Como se puede apreciar en la figura \ref{ae:flow} y en el algoritmo \ref{algorithm:evolutive} un EA comenzará con la inicialización de su población 
de manera aleatoria (aunque a menudo se utilice conocimiento particular
del problema para sesgar la búsqueda), a continuación se miden los valores de {\it fitness} para cada uno de los individuos de la 
población. La función de {\it fitness} puede ser un sencillo cálculo o tan compleja como realizar una serie de simulaciones.
La selección de los individuos se efectúa en dos fases: selección de padres y supervivencia. La selección de padres decide 
que individuos se convertirán en los padres, colocándolos en un conjunto conocido como {\it mating pool}.
Sobre este conjunto se aplican dos operadores: primero el de recombinación, que mezcla la información genética de los padres y en segundo lugar
el operador de mutación, que altera aleatoriamente los individuos. Obteniéndose como resultado el conjunto de hijos. 
Finalmente el algoritmo creará la siguiente población sustituyendo algunos individuos por los hijos, mediante una política de
reemplazo.

% El operador de mutación alterará a los hijos para
% que finalmente el algoritmo seleccione quienes sobreviven en la siguiente generación aplicando una política de reemplazo 
% en la población original por los hijos.

\begin{algorithm}
\footnotesize
\caption{Algoritmo Evolutivo}
\label{algorithm:evolutive}
\begin{algorithmic}

\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\FORALL{$p \in P(t)$}
\STATE evaluar fitness $p$
\ENDFOR 
\REPEAT

\STATE {\it mating pool} $=$ seleccionar padres $P(t)$
\STATE $hijos$ = recombinar {\it mating pool}
\STATE mutar $hijos$
\FORALL{$p \in hijos$}
\STATE evaluar fitness de $p$
\ENDFOR
\STATE $P(t+1)=$ reemplazar $P(t)$ con $hijos$
\STATE $t = t + 1$
\UNTIL{condición de término}

\end{algorithmic}
\end{algorithm}

Para resolver un problema de optimización utilizando un EA lo primero que debe establecerse es la representación de las soluciones,
es decir, la estructura que representará a una solución en el algoritmo. A las soluciones en el contexto de la computación evolutiva
se les llama fenotipos. Dado que potencialmente una solución candidata puede ser representada por una estructura muy compleja, se opera sobre una 
representación mas sencilla que en el ámbito de los EA se la conoce como genotipo. Los EA trabajan sobre los genotipos que consisten por ejemplo,
en arreglos de bits, vectores de valores reales o enteros, árboles, etc. Aplicar EA a un problema específico comienza por elegir la codificación
que tomarán las soluciones y los operadores evolutivos que se aplicarán a la codificación de las soluciones. 

La función de {\it fitness} es la que dirige la búsqueda hacia continuas mejoras sobre las soluciones existentes, es por ello una
parte crucial de la resolución de un problema de optimización con EA. En problemas reales {\it fitness} es la pieza de código que se
ejecutará el 90\% del tiempo de ejecución del algoritmo \cite{515097}, además es frecuente que esta función sea la única información que se posee
acerca del problema, por lo que es recomendable utilizar todos los conocimientos acerca del dominio del problema a la función de {\it fitness}.

El operador de recombinación (también conocido como operador de cruce o {\it crossover}) toma dos o mas soluciones 
(que se les llama padres) para producir hijos, a través de la mezcla de la información
contenida en los padres. La idea de fondo que explica el mecanismo de cruce es que los valores de {\it fitness} de los padres
están vinculados a partes que constituyen sus genotipos, a estas partes se las conoce como {\it building blocks} \cite{whitley01overview, 534133}, 
mezclar los {\it building blocks} de los padres potencialmente resultará en un aumento en el {\it fitness}. El operador de recombinación, es por lo
 tanto un operador que busca explotar la información acerca del problema contenida en la población. 

El cometido del operador de mutación es explorar el espacio de bús\-que\-da, la mecánica del operador de mutación consiste en una transformación
estocástica de la solución a la que se aplica. La transformación aplicada por el operador de mutación producirá una solución que contiene 
material genético de origen aleatorio, propiciando entonces la exploración del espacio de búsqueda.

Uno de los puntos críticos de la aplicación de EA a la resolución de problemas de optimización, es mantener diversidad en el contenido genético
 dentro de la población. En oposición a otros métodos de resolución de problemas de optimización los EA operan sobre un conjunto de soluciones, lo que
 les permite ser precisos y robustos. Sin embargo, si no se mantiene una correcta diversidad es posible que no se explore correctamente el espacio, 
 llevando a converger al EA a soluciones óptimas locales y no a soluciones óptimas globales. 
 Existen dos mecanismos para aumentar la diversidad: aumentar la probabilidad de mutación y sesgar la búsqueda de forma de favorecer a aquellas 
 soluciones que presentan material genético innovador \cite{515097}. 

%Existen diferentes aproximaciones a la aplicación de la computación evolutiva que manejan de forma diferente el balance exploración y explotación, la
%codificación y los operadores evolutivos, a continuación una clasificación de los distintos AE conocidos.

\subsection{Clasificación de EAs}

A partir de la década de 1950 surgen las primeras investigaciones sobre EAs, en base a esos trabajos
emergen en las últimas décadas varias líneas de investigación: programación evolutiva, 
estrategias evolutivas y algoritmos genéticos \cite{ck-evolutionary, spears93overview}. A pesar de compartir los conceptos y
mecanismos expuestos anteriormente, cada una de estas variantes implementa de manera diferente al EA. Las diferencias entre
las distintas aproximaciones surgen en casi todos los aspectos de los EA, incluyendo la representación de los individuos, 
los mecanismos utilizados en los operadores evolutivos y los mecanismos para determinar el {\it fitness} de una solución. A continuación se presenta una breve reseña de cada una
de las distintas líneas de investigación.

\subsubsection{Programación Evolutiva}
La programación evolutiva (EP por sus siglas en inglés) fue desarrollada a partir de las investigaciones de Fogel en 1966 \cite{Fogel_1966}. 
En esta variante generalmente se usan representaciones de los individuos con características
especificas. Por ejemplo, en problemas que involucran variables de decisión reales, los individuos en la población se codifican
como un arreglo de variables reales, análogamente en problemas de grafos o máquinas de estado se utilizan listas ordenadas que representan
los nodos recorridos por el algoritmo. Algoritmos basados en EP son frecuentemente utilizados como optimizadores, a pesar de que la concepción de la EP tuvo como
objetivo generar inteligencia artificial \cite{spears93overview}.

\begin{algorithm}
\footnotesize
\caption{Programación Evolutiva}
\label{algorithm::EP}
\begin{algorithmic}

\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\FORALL{$p \in P(t)$}
\STATE evaluar fitness $p$
\ENDFOR 
\REPEAT
\STATE $t = t + 1$
\STATE $P(t+1)$ = seleccionar padres a partir de $P(t)$
\STATE mutar $P(t+1)$
\FORALL{$p \in P(t+1)$}
\STATE evaluar fitness $p$
\ENDFOR
\STATE seleccionar supervivientes $P(t+1)$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}

En el algoritmo \ref{algorithm::EP} se presenta un ejemplo de un EP, en donde luego de la
 inicialización se seleccionan $N$ individuos que producirán luego de ser mutados $N$ hijos. De la unión de los padres y los hijos 
 se seleccionaran $N$ supervivientes probabilisticamente utilizando el {\it fitness} de cada uno de ellos, de forma
de favorecer en el proceso a los que posean un mayor valor de adaptación. Es importante notar la ausencia explícita del 
operador de recombinación, ya que en Programación Evolutiva el operador de mutación se supone lo suficientemente flexible como para producir
efectos similares a los del operador de recombinación \cite{ck-evolutionary}.

\subsubsection{Estrategias Evolutivas}

Las estrategias evolutivas (ES por sus siglas en inglés) se basan en las investigaciones hechas por Rechenberg en 1973 \cite{Rechenberg_1973},
en donde se proponía el uso de selección y mutación trabajando sobre una población de tamaño uno. Mas tarde Schweffel \cite{hansen:431} incorporó
la recombinación y poblaciones de más de un individuo. Debido a que en su concepción se aplicaban a problemas de optimización
en el campo de la hidrodinámica, las ES utilizan representaciones basadas en vectores de reales puesto que los problemas del área tienen variables
de decisión continuas, sin embargo es sencillo extender el uso de ES a otras representaciones \cite{spears93overview}.

\begin{algorithm}
\footnotesize
\caption{Estrategia Evolutiva}
\label{algorithm::ES}
\begin{algorithmic}

\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\FORALL{$p \in P(t)$}
\STATE evaluar fitness $p$
\ENDFOR 
\REPEAT
\STATE $t = t + 1$
\STATE {\it mating pool} = seleccionar padres a partir de $P(t)$
\STATE $P(t+1) = $recombinar {\it mating pool}
\STATE mutar $P(t+1)$
\FORALL{$p \in P(t+1)$}
\STATE evaluar fitness $p$
\ENDFOR
\STATE seleccionar supervivientes $P(t+1)$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}

El algoritmo \ref{algorithm::ES} muestra el pseudocódigo de un algoritmo basado en estrategia evolutiva. 
Después de la inicialización y evaluación, un ES selecciona los padres. A efectos de ejemplificar el algoritmo el operador de recombinación tomará $\mu$
padres para producir $\lambda$ hijos. Luego de la recombinación se aplica el operador de mutación sobre los hijos. 
Existen dos implementaciones para la selección de supervivientes: en la primer versión desarrollada por Rechenberg a partir
de $\mu$ padres se obtenía un hijo, en el caso que fuera mejor que los padres reemplazaría al peor de ellos,
 esta forma de reemplazo es conocida como $(\mu, \lambda)$ (con $\lambda = 1$);  en la segunda versión (hecha por Schweffel), a partir del conjunto unión de padres e hijos, se seleccionan aleatoriamente $N$ individuos, a esta estrategia de reemplazo se la llama $(\mu + \lambda)$.


La política de reemplazo $(\mu + \lambda)$ permite que el mejor individuo de la generación $t+1$ sea peor respecto al {\it fitness} que
el mejor individuo de la generación $t$. De este modo, el mecanismo no elitista permite que a lo largo de la evolución sean aceptables 
deterioros temporales en el {\it fitness} de la población, lo que ayuda a mitigar la convergencia a óptimos locales \cite{ck-evolutionary}. 
Por el contrario en la política $(\mu, \lambda)$, al ser sustituidos los peores individuos el {\it fitness} del mejor individuo es estrictamente
creciente a lo largo de las generaciones.


\subsubsection{Algoritmos Genéticos}

Los Algoritmos Genéticos (GA por sus siglas en inglés), de\-sa\-rro\-lla\-dos por Holland en 1975 \cite{129194} tradicionalmente utilizan como representación
vectores de bits de forma de ser independiente del dominio, sin embargo recientes aplicaciones de GA se han concentrado en otras representaciones
como grafos, expresiones Lisp, listas ordenadas y vectores de valores reales \cite{spears93overview}.

El algoritmo \ref{algorithm:ga} presenta un GA típico. Después de la inicialización se selecciona a los padres de acuerdo a una función
probabilística que utiliza el {\it fitness} relativo de las soluciones que está dada por:

$$P_{seleccion}(x) = {fitness(x) \over {\sum_{y \in poblacion} {fitness(y)}}}$$

De forma que individuos con un alto valor de {\it fitness} relativo tienen mas probabilidades de ser seleccionados
como padres. A partir de los $N$ padres se generan $N$ hijos vía recombinación. A los $N$ hijos se les aplica el operador
de mutación para mas tarde reemplazar a los $N$ padres. En GA se hace hincapié en el uso del operador de recombinación contrariamente
a lo que sucede en EP. En GA la mutación cambia bits de las soluciones con un probabilidad pequeña. Para GA la probabilidad de 
cruce ($p_c$) se recomienda que esté en el rango $[0.75, 0.95]$, en ES esa probabilidad frecuentemente toma valores cercanos
a $0.6$. Para el operador de mutación en GA se propone utilizar una probabilidad de mutación $p_m = 1/l$ donde $l$ es el 
largo del vector que representa a las soluciones
\cite{ck-evolutionary, 534133}.


\begin{algorithm}
\footnotesize
\caption{Algoritmo Genético}
\label{algorithm:ga}
\begin{algorithmic}

\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\FORALL{$p \in P$}
\STATE evaluar fitness $p$
\ENDFOR 
\REPEAT
\STATE {\it mating pool} $=$ seleccionar padres $P(t)$
\STATE $hijos$ = recombinar {\it mating pool}
\STATE mutar $hijos$
\FORALL{$p \in hijos$}
\STATE evaluar fitness de $p$
\ENDFOR
\STATE $P(t+1)=$ reemplazar $P(t)$ con los mejores $hijos$
\STATE $t = t + 1$
\UNTIL{condición de término}

\end{algorithmic}
\end{algorithm}

 

La fuerte preferencia por el uso de representaciones binarias de las soluciones en los Algoritmos Genéticos (GA) está 
vinculada a la teoría de los esquemas de los GA \cite{whitley01overview, 534133}, que intenta analizar el comportamiento 
de los GA en términos de esquemas, que son patrones que se repiten a lo largo de los individuos. Un esquema es un subconjunto
de $ {\lbrace 0, 1\rbrace}^{t} $ y la teoría de los esquemas de los algoritmos genéticos dice que en el GA canónico
 los esquemas de menor tamaño que compongan la solución óptima (denominados {\it building blocks} en la bibliografía) 
se reproducirán de forma exponencial a lo largo de las generaciones incrementando el {\it fitness} de los individuos.

En el GA Canónico, la mutación y la recombinación son aplicadas con un fuerte énfasis en la recombinación. Este algoritmo
utiliza el llamado {\it One Point Crossover} (SPX) como operador de cruce, en el cual se sortea
un punto de cruce $i$ y se producen dos individuos que mezclan los bits que componen a los padres como se muestra en  el
algoritmo \ref{algorithm::SPX}.

\begin{algorithm}
\footnotesize
\caption{{\it Single Point Crossover}}
\label{algorithm::SPX}
\begin{algorithmic}

\FOR {$k = 1$ hasta el tamaño de la solución}
\IF{$k <= i$}
\STATE $child0[k] = parent0[k]$
\STATE $child1[k] = parent1[k]$
\ELSE
\STATE $child0[k] = parent1[k]$
\STATE $child1[k] = parent0[k]$
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

En muchos problemas, los GA tienen la tendencia a converger a los óptimos locales en lugar de los globales, principalmente
sucede cuando no se mantiene una correcta diversidad entre los in\-di\-vi\-duos. Para paliar de alguna manera esta situación se introducen
diversos mecanismos; algunos intentan restringir el cruce a individuos que se ``parecen mucho'', e inclusive algunos introducen
una suerte de castigo a la selección de individuos parecidos, reduciendo de esta forma la representación de ese subconjunto
 en las siguientes generaciones. Otros métodos para aumentar la diversidad consisten en aumentos en la probabilidad de
mutación dinámicamente, de forma de que se produzcan nuevas soluciones a lo largo de las generaciones \cite{mahfoud95niching}.


\subsection{Explotación, exploración y {\it fitness}}

El objetivo de los EAs es producir soluciones con mejor {\it fitness}. Al esfuerzo de búsqueda del algoritmo en zonas que poseen un mayor 
{\it fitness} se le conoce como explotación (porque implica hacer uso del conocimiento que se tiene respecto al espacio de búsqueda). 
A la disposición del algoritmo a evaluar zonas del espacio de búsqueda nuevas o de bajo {\it fitness} se la conoce como exploración.
La ponderación que haga el algoritmo de la explotación está directamente vinculada entre otras cosas a los mecanismos de comparación de los valores de {\it fitness}.
Por ejemplo, dado un espacio de búsqueda que se describa a partir de una función $F$  y otro espacio idéntico pero descrito por la función $G = F^p$ con $p > 1$,
las zonas de mayor {\it fitness} son iguales. Dado que  las únicas diferencias entre un espacio y otro son las diferencias relativas de {\it fitness},
 un EA que potencie la explotación muestreara mejor las áreas con mayor {\it fitness} en el segundo espacio que en el primero puesto que en el segundo
 espacio las diferencias de {\it fitness} absoluta son mayores. 


En el caso de las ESs el operador de selección está basado en una ordenación por {\it fitness} de la población, 
 por lo tanto 
ESs buscarán de forma idéntica en los dos escenarios del ejemplo, la selección de supervivientes simplemente toma los $N$ mejores individuos
 \cite{spears93overview}. 

En el GA Canónico los espacios $F$ y $G$ son explorados de distinta forma. El operador de selección opera favoreciendo a las soluciones
 proporcionalmente a su calidad respecto al promedio. Uno de los problemas que plantea esta aproximación es que al avanzar en la búsqueda
las diferencias entre los valores de {\it fitness} se hacen mas pequeñas, bajando la explotación en la búsqueda. Este efecto se trata
de compensar mediante mecanismos que tienden a magnificar (método llamado {\it fitness scaling}) las diferencias a medida que la búsqueda avanza \cite{93136}. 

\subsection{Flexibilidad del enfoque}

La computación evolutiva simula la evolución natural con el objetivo de resolver problemas de búsqueda y optimización
en una va\-rie\-dad de áreas de aplicación. El gran éxito de las diferentes aproximaciones de los algoritmos evolutivos
indica que los principios subyacentes son genéricos y robustos, permitiendo la búsqueda en espacios tan arbitrarios
como: secuencias binarias, vectores de valores reales, permutaciones y otros \cite{ck-evolutionary}. 
Al contrario de lo que sucede con otras técnicas
de resolución, es posible con relativamente poca información acerca del problema a resolver, alcanzar niveles de precisión
arbitrarios con un uso adecuado del poder de cómputo \cite{spears93overview}. 

\section{Paralelismo aplicado a EAs}\label{PEA}

Se le llama paralelismo a un área de la informática cuya especialización es el diseño, implementación y ajuste de programas 
que aprovechan las posibilidades de las computadoras paralelas (ya sea multiprocesadores o multicomputadores \cite{6074}) 
de forma de ejecutar concurrentemente procesos que cooperan para ejecutar una tarea. Para ello particionan el problema
en tareas separadas, asignando tareas a procesadores y sincronizándolas para obtener resultados significativos.

Flynn en su trabajo de 1996 \cite{flynn96parallel} propone la clasificación de las distintas arquitecturas de paralelismo, 
  para clasificarlas utiliza un modelo basado en los diferentes flujos usados en los procesos computacionales.
 Un flujo es una secuencia de objetos, como por ejemplo datos o instrucciones. 
 Cada flujo es independiente de los otros y cada elemento del flujo puede constituirse por uno o 
 mas objetos. Existen cuatro combinaciones de estos elementos que describen las arquitecturas
 paralelas conocidas: 

\begin{enumerate}
\item{SISD} Una sola instrucción para un sólo flujo de datos ({\it Single Instruction Single Data} en inglés), esta 
combinación representa la computación con un sólo proceso o secuencial.

\item{SIMD} Una sola instrucción para múltiples flujos de datos ({\it Single Instruction Multiple Data} en inglés), normalmente
esta combinación se presenta en usos específicos como el procesamiento de gráficos, sonido o {\it stream processing} en general 
 que impliquen la aplicación de 
operaciones a varios flujos de datos, frecuentemente estas operaciones involucran cálculos vectoriales.

\item{MISD} Múltiples instrucciones para un sólo flujo de datos ({\it Multiple Instruction Single Data} en inglés),
representa a las arquitecturas paralelas que involucran a mas de un proceso interactuando con un sólo flujo de datos,
 generalmente se implementa sobre multiprocesadores dada la necesidad de compartir memoria.

\item{MIMD} Múltiples instrucciones para múltiples flujos de datos ({\it Multiple Instruction Multiple Data} en inglés), 
esta combinación referencia a arquitecturas paralelas que estén compuestas por varios procesos que interactúan con un conjunto
de datos.
\end{enumerate}

La tendencia actual en el hardware hacia los multiprocesadores y un aumento en la capacidad de interconexión entre computadoras permite
que, estas cuatro categorías de arquitecturas paralelas estén a disposición de los investigadores para
obtener mejoras en el rendimiento en la resolución de problemas con técnicas conocidas. Así como también, la investigación
de nuevas formas de explotar la capacidad teórica de cálculo subyacente a los centros de cómputo existentes.

 La mejora en el uso de los recursos computacionales obtenidos por la aplicación de técnicas de paralelismo se mide a través del {\it speedup}, que es
el cociente entre el tiempo medio de ejecución de la versión serial sobre la misma medida aplicada al algoritmo paralelo \cite{subhlok93exploiting, citeulike:1640567}. Cuando un algoritmo
presenta $speedup = m$ (siendo $m$ la cantidad de unidades de proceso que se utilizaron en el experimento) se dice que tiene un {\it speedup} lineal, cuando es inferior 
se le dice sublineal y si este valor es superior es superlineal \cite{tomassini99parallel}.

La evolución natural es intrínsecamente un proceso paralelo, cada individuo es seleccionado de acuerdo a su {\it fitness} para sobrevivir y reproducirse. Los EA son 
solamente una abstracción de este mecanismo, analizando cada solución fuera del contexto de la población, lo que permite que cada uno de estos análisis
sea realizado en una unidad de proceso independiente, por lo que los EA presentan características que los hace paralelizables.

Cuando se busca resolver problemas del mundo real, la capacidad de recursos informáticos puede verse sobrepasada por la complejidad de los algoritmos y/o al tamaño de las instancias a resolver, 
esta es la motivación principal para la aplicación de técnicas de paralelismo a los algoritmos evolutivos. 
Otra motivación es el beneficio que se obtiene desde el punto de vista algorítmico al aplicar el paralelismo a la computación evolutiva en analogía
 con la evolución natural que se da en poblaciones espacialmente distribuidas \cite{tomassini99parallel}.

Existen varias aproximaciones al paralelismo  para EA \cite{cantu-paz95summary, crainic98parallel, tomassini99parallel}. 
La forma mas sencilla consiste en mantener la población en una unidad de proceso y delegar funcionalmente la evaluación de {\it fitness}
a otros procesos, este método se llama paralelización global; otra aproximación al paralelismo llamada de grano grueso, consiste en mantener 
varias poblaciones evolucionando independientemente e intercambiando individuos de acuerdo a algún criterio. Finalmente, el modelo de grano fino
 es una técnica de paralelismo aplicado a EAs que  consiste en la partición de la población en pequeños subconjuntos entre
 los cuales se permite el cruce a las poblaciones màs cercanas, este modelo es conocido como paralelismo de grano fino. 
A continuación se profundiza en estos conceptos.


\subsection{Modelo Global}
%\subsection{Modelo master-slave}
El Modelo Global de paralelismo propone a partir del algoritmo evolutivo secuencial delegar la evaluación de los operadores genéticos y la asignación de {\it fitness} a otros procesos.
 Para ello se mantienen en un proceso, que se denomina Maestro a la población de individuos, como se puede observar en la figura \ref{paralelismo:master-slave} este
proceso enviará a los individuos a los procesos esclavos que se limitarán a realizar los cálculos necesarios sobre los individuos. En este modelo la comunicación 
existe solamente para enviar individuos y para recibir los resultados \cite{cantu-paz95summary}. 

\begin{figure}[h]
\centering
\includegraphics[scale=0.35]{images/Diagrama-Master-Slave.png}
\caption{Diagrama de distribución {\it master-slave}}\label{paralelismo:master-slave}
\end{figure}


La forma más sencilla de implementación del Modelo Global consiste en delegar la evaluación del {\it fitness} a los procesos esclavos 
(puesto que su operativa no depende de otros factores más que el individuo). Para ello el proceso maestro hará una partición
de la población para luego enviar los individuos a los esclavos, los que evaluarán el {\it fitness} de cada solución y devolverán los resultados al proceso maestro. 
Luego de recibir los resultados el proceso Maestro a su vez aplicará los operadores evolutivos (mutación y recombinación) para producir la siguiente generación \cite{534133}.

Implementaciones sofisticadas del Modelo Global tomarán en cuenta la carga de los esclavos para asignar
de manera inteligente los recursos, principalmente en el caso de procesadores con distinto poder de cómputo, debido a que los esclavos más rápidos o con menor carga
 culminarán la evaluación antes que los demás, desaprovechando ciclos de CPU mientras están inactivos hasta que arriben nuevos datos. 


En cuanto al {\it speedup} de este modelo es de esperar que sea en el mejor de los casos lineal, dependiendo de los requerimientos en poder de cómputo de los
procesos delegados contrapuestos con la sobrecarga del pasaje de datos, aspecto importante en el caso de que la plataforma sea multicomputador \cite{cantu-paz95summary}.

\subsection{Modelo de Grano Grueso}

Este modelo está inspirado en la forma de evolución natural en el escenario de varias islas relativamente aisladas una de otra.
A los algoritmos que siguen este paradigma se les llama distribuidos, puesto que son frecuentemente implementados en computadoras
 con memoria distribuida (multicomputadores). El modelo propone la separación de la población en subconjuntos sobre los cuales distintos 
procesos aplicarán el algoritmo evolutivo, la interacción entre los procesos es a través del envío de individuos entre un proceso (isla) y otro como se puede observar 
en la figura \ref{paralelismo:islas}. 
Este mecanismo introduce un nuevo operador al algoritmo que es el que se encarga de transportar los individuos entre islas y recibe el nombre de operador 
de migración, este operador es aplicado según una política que determina: cuales individuos son transportados y en que momento se produce la migración.

La incorporación del operador de migración al EA produce una restricción a la interacción entre la población: en el modelo
secuencial los individuos se recombinan sin importar su procedencia, puesto que no existen subconjuntos; por el contrario en el Modelo de Grano Grueso 
los individuos de subpoblaciones diferentes se podrán cruzar si uno de ellos migra a la isla del otro.
Esta limitante a la supone un cambio en la mecánica del algoritmo evolutivo secuencial \cite{cantu-paz95summary}.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{images/Diagrama-Islas.png}
\caption{Diagrama de distribución en islas}\label{paralelismo:islas}
\end{figure}

La política de migración trata de comunicar las soluciones que tienen características interesantes, de forma tal que en el resto de las islas se introduzca material
genético que produce características deseables. El intercambio de material genético a través de la migración tiene como resultado una evolución conjunta de las islas, 
pero a su vez debido a la restricción a la recombinación fomenta la diversidad de soluciones.

Existen migraciones sincrónicas y asincrónicas que varían en la metodología de intercambio de individuos. La migración sincrónica
implica que todas las islas detengan las respectivas evoluciones en un punto del tiempo para trasladar los individuos de una isla a otra.
Por el contrario, en la migración asincrónica las islas no detienen su evolución para transferir los individuos. 

El método más eficiente en cuanto al uso de los
 recursos computacionales es el que no implica una detención de la evolución por parte de las islas. Sin embargo, en condiciones en que los recursos computacionales
son he\-te\-ro\-gé\-neos, la evolución asincrónica implica para el algoritmo evolutivo la potencial evolución desfasada de individuos, aspecto peligroso considerando 
que la evolución en las islas más rápidas no toma en cuenta la carga genética de las islas más lentas por el evidente retardo. Para la 
evolución sincrónica, el mismo escenario genera una situación en que la velocidad total del sistema se corresponde con la del proceso más lento.


\subsection{Modelo de Grano Fino}\label{section:modelodegranofino}

El modelo de grano fino también conocido como modelo celular o de grilla, propone un esquema de separación de poblaciones, pero a diferencia del modelo de grano grueso no existe
 migración, sino que las poblaciones  se reproducen dentro de cierto alcance o vecindario. Mediante este mecanismo se difunden
 las mejores características genéticas a lo largo de las poblaciones. El modelo celular se asemeja vagamente a la forma de reproducción por
 po\-li\-ni\-za\-ción de algunas plantas, Goldberg \cite{534133} hace una analogía entre las lineas de comunicación entre las poblaciones y las rutas de los
 insectos encargados de la po\-li\-ni\-za\-ción de las plantas.

El modelo celular propone una modificación del operador de selección, el cual ya no solamente operará con la población actual, sino
que operará con un superconjunto de poblaciones que incluirá al de su propia instancia y a los de las instancias cercanas. En la figura \ref{paralelismo:celular}
se muestra un ejemplo de topología de subpoblaciones en un modelo de grano fino, en donde se representan las subpoblaciones con círculos rellenos y 
las líneas representan la red comunicación entre subpoblaciones. Además en la ilustración se marcan con elipses el alcance de dos vecindarios solapados. 

La segmentación que el modelo de grano fino establece una estructura espacial subyacente a los vecindarios vinculados. Son frecuentes las implementaciones del modelo de grano fino
 en una matriz de dos dimensiones, aunque también existen otras topologías posibles. La estructura de relaciones entre vecindarios determina directamente
 la velocidad de difusión de características exitosas de las soluciones, puesto que la probabilidad de cruce de dos soluciones en diferentes vecindarios es proporcional a la cantidad
de conexiones entre los mismos. 

El mecanismo de propagación de soluciones en el modelo de grano fino produce que la búsqueda en un EA paralelo implementado según este modelo se haga mas similar a la búsqueda en
 un EA secuencial a medida que aumenta la interconexión entre instancias \cite{tomassini99parallel}.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{images/Diagrama-Celular.png}
\caption{Ejemplo de topología en un Modelo de Grano Fino}\label{paralelismo:celular}
\end{figure}

%En el Modelo Celular a medida que aumenta la interconexión entre instancias las mejores soluciones se propagarán más rápido, lo que hace que la
%recorrida del espacio de búsqueda se haga mas similar a la que realiza un EA secuencial 

Para el modelo de grano fino un requisito fundamental es que sean accesibles las poblaciones de distintas instancias, lo que 
implica una alta exigencia sobre el medio de comunicación utilizado. La implementación de este modelo generalmente descansa sobre algún
sistema de memoria compartida, normalmente multiprocesadores, dado que cuentan con mayor capacidad de comunicación \cite{subhlok93exploiting}.


%Tanto el modelo de islas como el celular suponen un cambio en la forma en que se explora el espacio de soluciones, en el sentido de que
% cuando se utiliza el modelo secuencial un individuo se puede cruzar con cualquier otro, por el contrario estos métodos imponen
% restricciones a esta práctica. Este cambio a pesar de parecer sutil afecta directamente el balance explotación-exploración que
% utiliza el algoritmo secuencial. 

El éxito de la aplicación del paralelismo a los EA se ve reflejado en el volumen de investigación realizada en el área.
Alander en 1999 \cite{alander96indexed} compiló una extensa bibliografía sobre EA paralelos en donde se muestra
el rápido crecimiento de la investigación en el área, sobre todo en la última década. El análisis estadístico que realizó
el autor indica que el mayor esfuerzo de investigación se realiza sobre los modelos de paralelismo de grano grueso. 


\section{MOEAs}

La resolución de MOPs, ha implicado un esfuerzo continuo en diversas áreas, como resultado se han desarrollado poderosas
herramientas deterministas y estocásticas para hacer frente a los MOP de grandes dimensiones \cite{Coello_Coello_MOEA}. 

La gran evolución que tuvo el poder de cómputo en estas últimas décadas tuvo como consecuencia un incremento extraordinario en la investigación y 
desarrollo de algoritmos estocásticos, como aproximaciones a la resolución de problemas de optimización.

Actualmente existe una gran variedad de técnicas de cálculo nu\-mé\-ri\-co, sin embargo en general plantean
limitaciones al atacar el problema:

\begin{enumerate}
\item Son suceptibles a la forma del frente de Pareto. En situaciones en que el frente de Pareto es cóncavo o inconexo.

\item Requieren que se explicite información acerca de las funciones objetivo. Lo que no es siempre factible en problemas
reales.

\item Muchas técnicas de cálculo numérico obtienen una solución del frente de Pareto por cada ejecución, por lo que para encontrar
el frente de Pareto es necesario repetir la ejecución varias veces. En problemas de gran porte esto es una limitante.

\end{enumerate}
% Las técnicas deterministas plantean varias desventaja

%son susceptibles a la forma del frente de Pareto, o directamente no funcionan cuando el frente de Pareto
%es cóncavo o desconexo. Además las técnicas deterministas requieren que se explicite información acerca de las funciones objetivo, lo que en muchas situaciones reales no es factible. 
%Además la mayoría de ellas trabajan secuencial respecto a las soluciones, es decir, por cada corrida se obtiene una solución ({\it hill climbing}), 
%es entonces necesario al utilizar estas técnicas, realizar varias corrid\listofalgorithmsas con diferentes puntos de inicio para aproximarse al frente de Pareto. 

Como contraste a las desventajas de los métodos deterministas para resolver un MOP la computación evolutiva brinda una forma elegante, sencilla y rápida
de trabajar con conjuntos de soluciones. Además por el hecho de que no se necesita manejar información extra de las funciones objetivo (como por 
ejemplo el conocer las derivadas parciales) los algoritmos evolutivos no son tan susceptibles a la forma o continuidad del frente buscado. 
Lo que permite a los algoritmos evolutivos hacer muestreos mucho más fieles de los que se podría obtener con otros métodos \cite{thesis-banos}.

%\begin{figure}[h]
%\centering
%\includegraphics[scale=0.3]{images/Diagrama-EA-tasks.png}
%\caption{Tareas de un algoritmo evolutivo}\label{fig:EAtasks}
%\end{figure}

Anteriormente se estableció que un algoritmo evolutivo se puede descomponer en las tareas que se pueden observar en el pseudocódigo 
del algoritmo \ref{algorithm:evolutive}.
La diferencia medular entre los algoritmos con un solo objetivo y los multiobjetivo es que la función de {\it fitness} no siempre guarda
relación directa con la función objetivo como se puede observar en el algoritmo \ref{algorithm:moea}. En la mayoría de los algoritmos evolutivos de un sólo objetivo las funciones
que nos indican la adaptabilidad coinciden con la función a optimizar. Por el contrario, en la generalización del problema para considerar objetivos múltiples
existe un análisis intermedio que implica no solamente la evaluación de los $m$ objetivos involucrados, sino que también
se procede a algún tipo de consolidación de estos valores. Que respeta los principios evolutivos de forma de darle mejor valor de {\it fitness}
a los individuos más aptos.
% Esta variación históricamente no siempre se condujo a través 
% de los principios de Pareto por lo que es más correcto expresarlo genéricamente de la siguiente manera \cite{Coello_Coello_MOEA}.

\begin{algorithm}
\footnotesize
\caption{MOEA}
\label{algorithm:moea}
\begin{algorithmic}

\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\FORALL{$p \in P$}
\STATE evaluar funciones objetivo $p$
\STATE consolidar y asignar {\it fitness} $p$
\ENDFOR 
\REPEAT
\STATE $t = t + 1$
\STATE {\it mating pool} $=$ seleccionar padres $P(t)$
\STATE $P(t+1)$ recombinar {\it mating pool}
\STATE mutar $P(t+1)$
\FORALL{$p \in P(t+1)$}
\STATE evaluar funciones objetivo $p$
\STATE consolidar y asignar {\it fitness} $p$
\ENDFOR
\STATE seleccionar supervivientes $P(t+1)$
\UNTIL{condición de término}

\end{algorithmic}
\end{algorithm}



La aplicación de la computación evolutiva a los problemas multiobjetivo presenta dos grandes dificultades:  
cómo realizar la asignación de {\it fitness} y articular la selección de forma tal de dirigir la búsqueda
hacia el frente de Pareto y cómo mantener la diversidad de la población para prevenir la convergencia
prematura y poder alcanzar una buena distribución a lo largo del frente de Pareto, aprovechando la capacidad de los EA de manejar
un conjunto de soluciones \cite{ZDT_2000}. A continuación se detalla una clasificación de las diferentes aproximaciones
a la resolución de MOPS.

%Frecuentemente las diferentes aproximaciones a MOEA se clasifican en relación al criterio 
%de selección, en segundo orden a el criterio de consolidación de {\it fitness} y finalmente en relación a la selección utilizando
%los principios de Pareto \cite{ZDT_2000}. 

\subsection{Clasificación de MOEAs}

Se propone una clasificación de los algoritmos
 en función de la interacción con el usuario, es así que se definen tres categorías de MOEA, según el momento en que se
requiera la intervención humana: a \textit{priori}, progresivas y a \textit{posteriori} \cite{Coello_Coello_MOEA, vanveldhuizen99amultiobjective, vanveldhuizen98multiobjective, ZDT_2000}.

\subsubsection{Técnicas a {\it priori}}
Se basan en que el usuario consolida según su criterio los $m$ objetivos del problema en uno solo, reduciendo de esta 
manera un problema multiobjetivo a un problema de optimización clásico (con un solo objetivo). La agregación de
las funciones objetivo no siempre es una tarea trivial, sobretodo cuando la importancia de un objetivo 
sobre otro no es explícita o cuando no es factible establecer una relación entre objetivos \cite{Coello_Coello_MOEA}. 
Existen diversas técnicas que se clasifican como a {\it prriori}, la diferencia principal entre ellas es la forma de agregación
de las funciones objetivo, a continuación se listan las técnicas mas relevantes.

\paragraph{Ordenación}
Las técnicas dentro de esta categoría están basadas en que para cada objetivo el usuario asigna una prioridad
previamente a la optimización. Cuando se comparan soluciones, se utiliza el objetivo con mayor prioridad, si hay un empate
se utiliza el siguiente, etc. Este mecanismo se utiliza para guiar la búsqueda en el espacio de soluciones. 

\paragraph{Combinación lineal}
Esta forma de agrupación de objetivos implica la combinación de los $m$ objetivos en uno solo de forma lineal
en donde {\it fitness} se calcula como suma ponderada de los objetivos:

\begin{center}
     $$ fitness = \sum_{i=1}^{i=k} w_i f_i(x) $$ donde $w_i \geq 0$
\end{center}

Siendo $w_i$ los coeficientes de ponderación que representan la importancia relativa de las $k$ funciones objetivo del
problema, se asume que $\sum_{i=1}^{i=k} w_i = 1$

\paragraph{Combinación no lineal}
Este procedimiento de agregación incorpora los objetivos de manera no lineal, en una formulación frecuentemente derivada del ensayo y error de la agregación
de objetivos. Existen varias técnicas dentro de esta categoría por ejemplo la agregación por multiplicación en donde:

\begin{center}
     $$ fitness = \prod_{i=1}^{i=k} f_i(x) $$ 
\end{center}

{\it Target Vector} es una técnica de combinación no lineal que utiliza una distancia a la meta ({\it target}) como 
forma de métrica de {\it fitness}. {\it Target Vector} requiere que el usuario asigne metas de rendimiento a cada objetivo, 
para permitir que las soluciones sean evaluadas a través de la distancia (en cierta norma) a la meta establecida: 

\begin{center}
    $$ fitness = {|| [F(x) - g]W^{-1} ||}_{\alpha} $$
\end{center}

donde $g = (g_1, \cdots, g_k)$ es un vector que representa las metas y $W$ es una matriz de ponderaciones
sobre los objetivos y el operador norma es generalmente la distancia euclideana ($\alpha = 2$).

Las técnicas llamadas {\it Minimax} son otro ejemplo de técnicas de agregación que implica la minimización ponderada
del valor de las funciones objetivo y metas especificadas por el usuario, de forma que


\begin{center}
    $$ fitness = max_{i = 1, \cdots, m} {{f_i(x) - g_i} \over {w_j}} $$
\end{center}

Donde $g_i$ es la meta a alcanzar o mejorar por el objetivo $i$ y $w_i$ es un valor de ponderación que indica
la dirección deseada en el espacio de búsqueda, utilizándose frecuentemente $w_j = ||g_j||$ \cite{vanveldhuizen98multiobjective}.

Las técnicas de agregación tienen como principal falla el hecho que llevan a cabo una búsqueda no uniforme sobre el espacio del problema puesto
que suponen un orden de relevancia de las funciones objetivo. De esta manera, aceptan que una solución sea buena según
cierto objetivo y sin embargo no lo sea según otro, por lo que alcanzar el frente de Pareto depende de la forma
en que se consoliden las funciones. Por otro lado si es aceptable que se optimice con mayor importancia un objetivo 
sobre otro, antes de aplicar esta técnica se debería de considerar la aplicación de un EA clásico u otro método 
de re\-so\-lu\-ción de problemas de optimización de un solo objetivo \cite{Coello_Coello_MOEA}.



\subsubsection{Técnicas progresivas}
El mecanismo de las técnicas progresivas implica la intervención humana durante la búsqueda del frente de Pareto, estableciendo sesgos o direcciones
en el espacio que se desea optimizar. La intervención a menudo toma la forma de decisiones sobre el valor de {\it fitness}
de una solución sobre otra o por medio de la selección de subconjuntos del espacio de búsqueda que se desea evaluar.
Se pueden utilizar en conjunto con técnicas a {\it{priori}} o {\it posteriori}.


\subsubsection{Técnicas a {\it posteriori}}
Las técnicas a {\it posteriori} no requieren intervención humana hasta que se presentan los resultados, para ello
buscan  encontrar ex\-plí\-ci\-ta\-men\-te el frente de Pareto para que el tomador de decisiones elija la solución
que sea más aceptable al problema, lo que implica que el usuario solamente deberá determinar cuál de las soluciones que
son óptimas de Pareto es la más adecuada como solución al MOP. Diversos métodos se encuentran en esta clasificación,
se detallan a continuación los más relevantes.

\paragraph{Muestreo Independiente}
A partir de un problema de optimización con $m$ objetivos, las técnicas de Muestreo Independiente asignarán {\it fitness} a las soluciones en una generación
utilizando uno de los objetivos, el cual cambiará en generaciones siguientes según cierta política. 
Como resultado de esta metodología la búsqueda en el espacio de soluciones hecha por el MOEA tenderá a encontrar el frente de Pareto. 
Las técnicas de Muestreo Independiente se aplican frecuentemente a problemas de complejidad desconocida.

%Las técnicas de Muestreo Independiente están basadas en la idea de a partir de un problema de optimización con $m$ 
%objetivos optimizar en una generación uno sólo de ellos, intercambiando el criterio de optimización según cierta política,
%como resultado la búsqueda tenderá a encontrar el frente de Pareto. Las técnicas de Muestreo Independiente se aplican
%frecuentemente a problemas de complejidad desconocida.
%Estas estrategias utilizan hacen varias búsquedas, cada una de ellas optimiza un solo objetivo, con el tiempo
%se alcanza el frente de Pareto y se le presenta al tomador de decisiones, se aplican frecuentemente a problemas
%nuevos de complejidad desconocida.

\paragraph{Selección de Criterio}
Las técnicas de Selección de Criterio aprovechan la capacidad de los EA de manejar un conjunto de soluciones para ello
dado un MOP con $m$ objetivos se fracciona la población en $m$ subconjuntos, (para generar el subconjunto $i$ se seleccionan
las mejores soluciones según el objetivo $i$). Luego del fraccionamiento de la población aplican los operadores evolutivos habituales 
y se vuelve a mezclar la población. La aplicación de esta metodología produce que se encuentren varios elementos del frente en una sola ejecución del algoritmo.
La principal desventaja del método es que se producen soluciones que son buenas según algunos criterios y no tanto
 en otros, por lo que no siempre se alcanza al frente de Pareto completamente, dado que la búsqueda no es uniforme en el espacio de soluciones puesto que 
no se ven representados individuos con rendimiento medio según los objetivos \cite{Coello_Coello_MOEA}.

\paragraph{Agregación de Selección}
Al igual que las técnicas de selección de criterio, las estrategias de agregación de selección aprovechan la capacidad de los EA para manejar un conjunto de soluciones.
La diferencia es que en esta metodología las poblaciones se seleccionan a partir de la combinación lineal o no lineal
de las funciones objetivo, permitiéndole encontrar varios miembros del frente de Pareto en una sola ejecución. Una particularidad
de este método es que la estrategia de agregación de funciones objetivos puede variar de una generación a otra.


\paragraph{Muestreo de Pareto}
Las técnicas de muestreo de Pareto se caracterizan por dirigir la búsqueda a través de la relación de dominación de Pareto, para converger
al frente de Pareto explícitamente. Para garantizar la permanencia de soluciones no dominadas y así asegurar la convergencia, frecuentemente utilizan un conjunto aparte de la población
para mantener las soluciones no dominadas hasta el momento.
%Existen dos tipos de asignación de {\it fitness} en estas técnicas. La primera, propuesta por Goldberg \cite{534133}, 
%consiste en asignar el valor $1$ a todas las soluciones no dominadas de la población y $0$ al resto. La segunda 
%propuesta hecha por Fonseca y Fleming \cite{} asigna el valor de {\it fitness} como la suma de
%la cantidad de elementos dominados por esa solución en la población actual.

La aplicación de los principios de Pareto en las técnicas de muestreo de Pareto se puede observar en los métodos de asignación de {\it fitness}, 
para calcular el {\it fitness} en estas técnicas se utiliza como función base el rankeo de Pareto (propuesto por Goldberg \cite{534133}) que toma como entrada un individuo de la 
población y se calcula de la siguiente manera: si un individuo $x_i$ en la generación $t$ es dominado por $p_i$ individuos en la generación
 $t$ entonces $ rank(x_i , t) = 1+p_i $ \cite{fonseca95overview}.

La evolución natural mantiene un conjunto diverso de especies que ocupan un lugar distinto dentro del ecosistema. Sin embargo,
en el EA típico se converge a una población uniforme, que consiste en varias copias del grupo más exitoso de soluciones, lo que 
implica que el espacio de búsqueda no sea explorado de manera adecuada, produciéndose potencialmente una convergencia prematura.
Una solución a ese problema es aplicar técnicas de nicho, que intentan mantener una correcta diversidad
en los individuos de la población simulando la competencia por recursos limitados. {\it Fitness sharing} es una técnica que permite alcanzar este 
objetivo ``compartiendo'' el {\it fitness} dentro de un conjunto de individuos de características similares (el nicho). 
El {\it fitness} compartido se calcula mediante la expresión: 

\begin{center}
    $$ fitness(x_i) = fitness'(x_i) / NC_i$$
\end{center}

Donde $NC_i$ es el {\it niche count}, que es una medida de cuán saturado está el nicho del individuo $i$ y $fitness'$ es la
función de {\it fitness} original \cite{42519}.

\paragraph{Selección basada en rankeo de Pareto y Nichos}
Las técnicas que utilizan selección basada en rankeo de Pareto y nichos realizan la asignación de {\it fitness} utilizando 
la función $rank$ y técnicas de nichos, de forma tal de buscar el frente de forma similar a las técnicas de muestreo de Pareto, 
pero intentando a su vez mantener la diversidad en la población
con el objetivo que el conjunto de individuos presentado como solución sea un muestreo uniforme del frente de Pareto.


\subsection{MOEAs basados en muestreo de Pareto}

Los algoritmos que se presentan a continuación se pueden clasificar dentro de la categoría de MOEAs basados en muestreo
de pareto o rankeo de pareto. 

Se pueden separar tal y como propone Coello \cite{Coello_Coello_Historical, state_of_the_art_2000},  
considerando el orden cronológico y los avances en computación evolutiva aplicados a los mismos. Este orden se puede disgregar
en dos generaciones que se describen a continuación.

\subsubsection{Primera generación}

Las primeras propuestas de MOEAs se podrían categorizar dentro de agregación de funciones, aunque se podían ver estrategias basadas en 
orden lexicográfico. En 1985 Schaffer \cite{657079} propone un algoritmo llamado {\it Vector Evaluated Genetic Algorithms} (VEGA) 
dentro de la categoría de selección de criterio que representaba el estado del arte para MOEAs en ese momento. 
En 1989 Goldberg \cite{534133} incorporó el muestreo de Pareto al proponer el rankeo de Pareto como estrategia de asignación
de {\it fitness}. Goldberg además, detalla sin dar implementaciones las ideas que prevalecieron durante esa época: 
la ordenación por dominación de Pareto y el uso de {\it fitness sharing} para disminuir la tendencia a la convergencia prematura. 
La influencia de su trabajo se vio reflejada en casi todos los MOEAs de la primer generación siendo su espacio cronológico de 1989 hasta 1998.
A continuación se detallan las propuestas mas relevantes de la primera generación de MOEAs basados en muestreo de Pareto.

\paragraph{Multiobjective genetic algorithm (MOGA)}
MOGA surge como propuesta de Fonseca y Fleming en 1993 \cite{Fonseca_1993}. El mecanismo de asignación de {\it fitness} que se propone ordena
 a los individuos de acuerdo a la función $rank$, el pseudocódigo de MOGA se puede observar en el algoritmo \ref{algorithm:MOGA}. 
Todos los individuos no dominados, tienen el valor de {\it fitness} máximo, mientras los dominados son penalizados
de acuerdo a la densidad de la región del espacio a la que pertenecen ({\it fitness sharing}).

La asignación de {\it fitness} propuesta involucra los siguientes pasos:
    \begin{enumerate}
        \item Ordenar la población de acuerdo al valor de $rank$
        \item Asignar valores de {\it fitness} interpolando desde el valor de $rank = 1$ hasta el valor de $rank$ más alto,
             (Goldberg propone utilizar una interpolación lineal \cite{534133}).
        \item Promediar individuos con el mismo $rank$ para que todos queden muestreados al mismo rango.
        Este procedimiento mantiene el {\it fitness} global constante mientras asegura una diversidad
        adecuada.
    \end{enumerate}


\begin{algorithm}
\footnotesize
\caption{MOGA}
\label{algorithm:MOGA}
\begin{algorithmic}
\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Asignar $Rank$ $ \forall p \in P(t)$
\STATE Calcular la cantidad de nichos
\STATE Asignar {\it fitness} linealmente escalado $\forall p \in P(t)$ 
\STATE Asignar {\it shared fitness} $\forall p \in P(t)$ 
\REPEAT
\STATE $t = t + 1$
\STATE {\it mating pool} $=$ seleccionar padres $P(t)$
\STATE $P(t+1) = $ recombinar {\it mating pool}
\STATE mutar $P(t+1)$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Asignar $Rank$ $ \forall p \in P(t)$
\STATE Calcular la cantidad de nichos
\STATE Asignar {\it fitness} linealmente escalado $\forall p \in P(t)$ 
\STATE Asignar {\it shared fitness} $\forall p \in P(t)$ 
\STATE seleccionar supervivientes $P(t+1)$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}


\paragraph{Nondominated Sorting Genetic Algorithm (NSGA)}\label{section:NSGA}

Srinivas y Deb \cite{srinivas94multiobjective} propusieron otra variación de la aproximación de Goldberg. En la cual antes de que se
produzca la selección se ``rankea'' la población según los criterios de dominio de Pareto. Los
individuos no dominados se clasifican en una categoría y se quitan de la población principal y con el resto se repite el 
procedimiento.Dado que los individuos no dominados
 tienen {\it fitness} máximo tienen más copias que el resto de la población (dependiendo del nivel de elitismo del operador de selección), 
es posible encontrar regiones no dominadas hacia las cuales tenderá a converger NSGA (ver algoritmo \ref{algorithm:NSGA}).


\begin{algorithm}
\footnotesize
\caption{NSGA}
\label{algorithm:NSGA}
\begin{algorithmic}
\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Asignar $Rank$ en base a la dominación de Pareto en cada ``ola''
\STATE Calcular el cardinal de cada nicho
\STATE Asignar {\it shared fitness}  $\forall p \in P(t)$ 
\REPEAT
\STATE $t = t + 1$
\STATE {\it mating pool} $=$ seleccionar padres $P(t)$
\STATE $P(t+1) =$ recombinar {\it mating pool}
\STATE mutar $P(t+1)$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Asignar $Rank$  $\forall p \in P(t)$
\STATE Calcular el cardinal de cada nicho
\STATE Asignar {\it fitness} linealmente escalado $\forall p \in P(t)$ 
\STATE Asignar {\it shared fitness} $\forall p \in P(t)$ 
\STATE seleccionar supervivientes $P(t+1)$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}


\clearpage
\paragraph{Niched Pareto genetic algorithm (NPGA)}
Horn, Nafpliotis y Goldberg en 1994 \cite{horn94niched} proponen un MOEA llamado NPGA, que utiliza al igual que MOGA y NSGA los 
principios de Pareto en la búsqueda dentro del espacio de soluciones, aunque en lugar de aplicarlo en la asignación de valores de {\it fitness} NPGA utiliza un operador
 de selección basado en torneo que se vale de la dominación de Pareto. 
El mecanismo de este operador de selección como se puede apreciar en el algoritmo \ref{algorithm:NPGA}, consiste en seleccionar aleatoriamente dos 
individuos de la población los cuales se comparan por dominación
contra un subconjunto de la población que llamaremos muestra. Este conjunto es elegido también aleatoriamente y típicamente su tamaño es del orden del 10\% de la población.
El operador de selección que utiliza NPGA seleccionará a aquel individuo que no sea dominado por ningún individuo del conjunto muestra, en el caso que ambos individuos
cumplan con esa condición el operador seleccionará a aquel cuyo cardinal de nicho ({\it niche count}) sea inferior.



\begin{algorithm}
\footnotesize
\caption{NPGA}
\label{algorithm:NPGA}
\begin{algorithmic}
\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Calcular el {\it niche count} de cada nicho
\REPEAT
\STATE $t = t + 1$
\REPEAT
\STATE Seleccionar dos candidatos y el conjunto $muestra$
\IF{sólo el $candidato_1$ no es dominado $\forall x \in muestra$}
\STATE $candidato_1$ se incluye en el {\it mating pool}
\ELSIF{sólo $candidato_2$ no es dominado $\forall x \in muestra$}
\STATE $candidato_2$ se incluye en el {\it mating pool}
\ELSE
\STATE aquel candidato que presente menor {\it niche count} se incluye en el {\it mating pool}
\ENDIF
\UNTIL{el {\it mating pool} está completo}
\STATE $P(t+1) =$ recombinar {\it mating pool}
\STATE mutar $P(t+1)$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Calcular {\it niche count} de cada nicho
\STATE seleccionar supervivientes $P(t+1)$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}


\subsubsection{Segunda generación}

La segunda generación de los MOEAs basados en rankeo de Pareto abarca cronológicamente  desde 1998 hasta la fecha y se caracteriza
por incorporar el elitismo. 
La aplicación del elitismo en el contexto de los MOEA surge a partir de los trabajos de Zitzler y Thiele en 1999 \cite{Zitzler_SPEA} y se refleja en el uso directo o indirecto de un subconjunto
de la población que mantiene a los individuos no dominados encontrados hasta el momento. La necesidad del
subconjunto de individuos no dominados reside, en que no hay garantías de que una solución no dominada en la generación $t$ también lo sea en las
generaciones previas o posteriores. El uso de un conjunto externo para las soluciones no dominadas, implica que el conjunto de soluciones que se le
 presenta al usuario como resultado comprende todas las soluciones no dominadas encontradas. A continuación se analizan las propuestas mas 
relevantes de los MOEAs pertenecientes a la segunda generación.

%El uso de este conjunto es una forma sencilla que garantiza que cuando se presente
%al usuario los resultados no se habrá perdido ninguna solución no dominada.
%La segunda generación de los MOEA basados en rankeo de Pareto que cronológicamente abarca desde 1998 hasta la fecha, se caracteriza
%por incorporar el elitismo a MOEA como un mecanismo estándar. A partir de los trabajos de Zitzler en 1999 \cite{Zitzler_SPEA} en
%los que presenta el algoritmo {\it Strength Pareto Evolutionary Algorithm} (SPEA), que demuestran los beneficios de la
%aplicación del elitismo, su aplicación en el contexto de los MOEA se refleja en el uso directo o indirecto de un subconjunto
%de la población que mantiene a los individuos no dominados encontrados hasta el momento, de forma tal de que en cualquier generación
%el frente conocido se tiene accesible para poder ser actualizado con los datos de la población actual. La necesidad de este
%subconjunto reside en que no hay garantías de que una solución no dominada en la generación $t$ también lo sea en las
%generaciones previas o posteriores, el uso de este conjunto es una forma sencilla que garantiza que cuando se presente
%al usuario los resultados no se habrá perdido ninguna solución no dominada.


%Comienza con el elitismo como un mecanismo estándar, dados los beneficios comprobados que produjo su introducción se  
%observar en los primeros trabajos sobre SPEA \cite{Zitzler_SPEA} ({\it Strength Pareto Evolutionary Algorithm}). 
%Es un mojón muy importante en el área, inclusive se ha demostrado que el elitismo es una condición necesaria para asegurar
%convergencia en computación evolutiva.  En el contexto de la optimización multiobjetivo, el uso del elitismo implica 
%el uso de una población externa, también conocida como población secundaria. Usada para retener a los individuos no dominados
%durante el proceso de evolución. La motivación principal de éste mecanismo es que una solución que es no dominada con respecto a la
%población actual, no es garantía de que sea para todas las poblaciones anteriores y futuras, un concepto sencillo que garantiza
%que las soluciones que se reportan al usuario son en efecto no dominadas, por lo menos en lo que al espacio de búsqueda recorrido
%significa. Por supuesto que lo mas lógico y sencillo es mantener un conjunto externo para colocar allí nuestra elite. 

\paragraph{Strength Pareto Evolutionary Algorithm (SPEA)}
En 1999 Zitzler y Thiele \cite{Zitzler_SPEA} proponen SPEA, este algoritmo se concibe como una forma de integrar distintos MOEA.
Para calcular el {\it fitness} de un individuo SPEA utiliza el valor {\it strength} (fortaleza) que se calcula como la cantidad de individuos que domina. Aquellos individuos que no son dominados
por ninguna solución de la población se incorporan al archivo de individuos dominantes, como se puede observar en el algoritmo \ref{algorithm:SPEA}.

Para mantener el conjunto de individuos dominantes, al detectar un individuo $i$ con éstas características antes de incorporarlo se retiran los 
individuos dominados por $i$. Además para mantener controlado el cardinal del conjunto se retiran individuos utilizando técnicas de {\it clustering} de 
forma  de eliminar individuos similares. Para conservar la diversidad en la población SPEA compone el {\it mating pool} con individuos de la población e individuos dominantes.



\begin{algorithm}
\footnotesize
\caption{SPEA}
\label{algorithm:SPEA}
\begin{algorithmic}
\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\STATE Inicializar el conjunto $E$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Calcular {\it strength} $\forall p \in P(t)$
\REPEAT
\STATE Copiar los individuos no dominados de $P(t)$ a $E$
\STATE Retirar elementos de $E$ que son dominados por otro elemento de $E$
\STATE Podar $E$ usando {\it clustering} cuando se exceda la capacidad máxima de $E$ 
\STATE Seleccionar de $P(t) \cup E$ el {\it mating pool}
\STATE Aplicar recombinación y mutación
\STATE Seleccionar supervivientes $P(t)$
\STATE $t = t + 1$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}


Zitzler y Thiele en 2001 \cite{Zitzler_SPEA2} propusieron otra versión de SPEA llamada SPEA 2 que se puede ver en el algoritmo \ref{algorithm:SPEAII} 
que se diferencia en los siguientes aspectos:
\begin{enumerate}
    \item Incorpora una asignación de {\it fitness} más fina, que toma en cuenta por cada individuo la cantidad
        de elementos dominados y  además la cantidad de elementos que lo dominan, de forma de fomentar
        aún más la exploración.
    \item Utiliza técnicas para garantizar la preservación de soluciones de borde.
\end{enumerate}


\begin{algorithm}
\footnotesize
\caption{SPEA 2}
\label{algorithm:SPEAII}
\begin{algorithmic}
\STATE $t = 0$
\STATE Inicializar la población $P(t)$
\STATE Inicializar el conjunto $E$
\STATE Evaluar funciones objetivo $\forall p \in P(t)$
\STATE Calcular {\it strength} $\forall p \in P(t)$
\REPEAT
\STATE Copiar los individuos no dominados de $P(t)$ a $E$
\STATE Retirar elementos de $E$ que son dominados por otro elemento de $E$
\STATE Podar $E$ usando {\it clustering} cuando se exceda la capacidad máxima de $E$ 
\STATE Si la capacidad de $E$ no se excedió usar elementos dominados en $P$ para llenar $E$
\STATE Seleccionar de $P(t) \cup E$ el {\it mating pool}
\STATE Aplicar recombinación y mutación
\STATE Seleccionar supervivientes $P(t)$
\STATE $t = t + 1$
\UNTIL{condición de término}
\end{algorithmic}
\end{algorithm}
\clearpage

\paragraph{NSGA II}
Deb \cite{Deb_2000} propuso una versión de NSGA, actualizada con los resultados del trabajo de Zitzler \cite{Zitzler_SPEA} (que dan origen a la segunda generación).
En la propuesta de Deb a diferencia
del enfoque utilizado por Zitzler y Thiele, no se hace un conjunto explicito para separar a los individuos dominantes de la generación.
Sin embargo, mediante la asignación de {\it fitness} se pondera a los individuos dominantes de cada generación de forma que tengan mayores probabilidades de ser seleccionados. 
Para evitar que el elitismo haga perder balance al algoritmo, se utiliza un mecanismo para mantener la diversidad, que se basa en favorecer en la selección a aquellos individuos
que pertenecen a un nicho poco poblado. El pseudocódigo de NSGA II se puede ver en el algoritmo \ref{algorithm:NSGAII}, aunque se volverá sobre él 
en la sección \ref{subsection:NSGAII_revisitado} para detallar su implementación.

\begin{algorithm}
\footnotesize
\caption{NSGA II}
\label{algorithm:NSGAII}
\begin{algorithmic}
\STATE $Inicializar(P(0))$
\STATE $generacion = 0$
\STATE $Evaluar(P(0))$
\REPEAT
\STATE $R = Padres \cup Hijos$
\STATE $Frentes = Sorting No Dominado(R)$
\STATE $NuevaPop = \emptyset$
\STATE $i=1$
\WHILE{$|NuevaPop| + |Frentes(i)| <= sizepop$}
\STATE $Calcular Distancia De Crowding (Frentes(i))$
\ENDWHILE
\STATE $NuevaPop = NuevaPop \cup Frentes(i)$
\STATE $i = i+1$
\STATE $Sorting Por Distancia (Frentes(i))$
\STATE $NuevaPop = NuevaPop \cup Frentes(i)[1:(sizepop - |NuevaPop|)$
\STATE $Hijos = Seleccion Y Reproduccion(NuevaPop)$
\STATE $generacion = generacion+1$
\STATE $P(generacion) = NuevaPop$
\UNTIL{${CriterioParada}$}
\end{algorithmic}
\end{algorithm}
\clearpage

\clearpage
\subsection{Comparación de MOEAs}

A pesar de la gran variedad de técnicas expuestas para resolver problemas multiobjetivo utilizando algoritmos 
evolutivos, hasta el arribo de la segunda generación, no existían mecanismos para evaluar el rendimiento
de los MOEA. Es en esa época que se comienza a generar un interés sobre el tema.

\subsubsection{Métricas}\label{section:Metricas}
La comparación entre dos algoritmos no es una tarea sencilla, ya que implica que existen medidas o indicadores 
que permitan determinar si un algoritmo es mejor que otro. En otras palabras lo que se necesita es definir el 
concepto de rendimiento en el contexto de los problemas multiobjetivo.

%En principio no es un problema sencillo de atacar, es decir, dados dos algoritmos, como evaluar cual es el mejor?. Claramente 
%se intenta enfrentarlos a los mismos problemas, pero aún así, es necesario definir que es lo que nos interesa, o en otras palabras
%necesitamos una definición de {\it performance} para MOEAs.

Dos situaciones distintas que presentan la necesidad de comparar las soluciones encontradas por dos algoritmos
 distintos bajo condiciones idénticas, servirán para exponer la dificultad de la comparación de MOEAs.

\begin{description}
\item Para el primer caso los frentes de Pareto encontrados por los algoritmos y el frente de Pareto real se
 presentan en la figura \ref{fig:frentes-1}, en este caso resulta lógico 
afirmar que el algoritmo 1 es mejor que el algoritmo 2, puesto que el frente encontrado por el algoritmo 1
 presenta mayor cantidad de individuos y además los mismos están más cerca del frente de Pareto, que los 
del algoritmo 2.

\item En un segundo caso presentado en la figura \ref{fig:frentes-2} la decisión no es tan
trivial, ya que el algoritmo 1 presenta una mayor cantidad de soluciones en el frente de Pareto encontrado,
 pero a mayor distancia del frente de Pareto real que algunas soluciones encontradas por el algoritmo 2.
\end{description}

En el primer caso la comparativa de MOEAs es bastante sencilla, en el segundo se hace imperativo para poder
compararlos la definición de índices, que permitan medir distintos aspectos de los resultados, como por ejemplo
la cantidad de puntos del frente de Pareto encontrado, la distancia de los mismos al frente de Pareto real 
la densidad de los  mismos, etc.



%Supongamos que estamos comparando los frentes encontrados por dos algoritmos diferentes, obviamente generados bajo condiciones similares,
%tamaño de población, cantidad de generaciones, probabilidad de mutación y recombinación, etc. Si nos encontramos ante ante la situación descripta 
%en la figura \ref{fig:frentes-1}, resulta lógico afirmar que el algoritmo 1 es mejor que el algoritmo 2, ahora bien, la decisión 
%no es trivial cuando nos enfrentamos a algo como la figura \ref{fig:frentes-2}.


\begin{figure}[h]
\centering
\includegraphics[scale=0.40]{images/fronts1.png}
\caption{Frentes de Pareto, caso uno}\label{fig:frentes-1}
\end{figure}


\begin{figure}[h]
\centering
\includegraphics[scale=0.40]{images/fronts2.png}
\caption{Frentes de Pareto, caso dos}\label{fig:frentes-2}
\end{figure}


\clearpage


Varios investigadores \cite{Coello_Coello_MOEA, Fonseca_1993, vanveldhuizen99multiobjective} proponen un conjunto de métricas
que permiten comparar MOEAs, las métricas propuestas toman en cuenta distintos aspectos de los resultados de un MOEA, que se
detallan a continuación.


\paragraph{Número de puntos no dominados}

Esta medida es la cantidad efectiva de puntos que contiene el frente de Pareto encontrado. Es una forma
 cuantitativa de medir el frente y no guarda relación con el frente de Pareto real, pero es importante
 conocerla porque da un índice de diversidad en las soluciones del frente encontrado, fomentando de esa manera
 el balance entre explotación y exploración del
 algoritmo. Al conjunto de puntos no dominados del frente de Pareto hallado se le llama $PF_{known}$ y a su
 cardinal $q$.

\paragraph{Distancia generacional}

Se propone medir la distancia de los puntos no dominados hasta el frente de Pareto real $PF_{true}$,
utilizando la distancia euclidiana en el espacio de los objetivos. El propósito de esta medida es dar una idea
 certera respecto a la veracidad de los puntos en $PF_{known}$. La distancia generacional se calcula mediante
 la expresión \ref{equation:GD}.

\begin{equation}
\label{equation:GD}
GD = {\sqrt{\displaystyle\sum_{x \in PF_{known}}{d_{x}^{2}}} \over {q}}
\end{equation}

Donde $d_{x}$ se calcula utilizando el punto de $PF_{true}$ más cercano $x_{true}$, siendo $x.m$ el valor que
 toma $x$ en la función objetivo $m$ y $M$ el conjunto de las funciones objetivo del problema, mediante la 
 expresión \label{equation:d_x}.

\begin{equation}
\label{equation:d_x}
d_{x} = \sqrt{\displaystyle\sum_{m \in M}{(x_{true}.m - x.m)^2}}
\end{equation}


\paragraph{Spacing} esta métrica mide la distancia entre los puntos de $PF_{known}$, se calcula según la expresión \ref{equation:spacing}.
En donde $\bar{d}$ es el promedio de $d_x$ para todos los puntos en $PF_{known}$ y $d_x$ se calcula mediante la ecuación \ref{equation:spacing:d_x}.

\begin{equation}
\label{equation:spacing}
spacing = \sqrt{{1 \over {1-q}} \sum_{x \in PF_{known}} {{(\bar{d} - d_x)}^2} }
\end{equation}


\begin{equation}
\label{equation:spacing:d_x}
d_x = min_{\forall y \in PF_{known}}( \displaystyle\sum_{m \in M}{|x.m - y.m|}) 
\end{equation}

{\it Spacing} es útil para medir la uniformidad en distribución de los puntos a lo largo de $PF_{known}$.
Un valor de cero en $spacing$ implica que todos los puntos encontrados guardan la misma distancia entre sí.


\paragraph{Spread} Es similar a $spacing$, pero incorpora la distancia a los extremos teóricos del frente de
 Pareto real. De esta forma no sólo se mide la distribución de los puntos de $PF_{known}$ sino que también se
 mide cuan bueno es el muestreo de $PF_{true}$. {\it Spread} se calcula a través de la  expresión \ref{equation:spread}.

\begin{equation}
\label{equation:spread}
spread = {{\displaystyle\sum_{e \in E} { \displaystyle\sum_{m \in M} {d_m^{e}}} + \displaystyle\sum_{x \in PF_{known}}{ | \bar{d} - d_x|} } \over 
            {\displaystyle\sum_{e \in E} { \displaystyle\sum_{m \in M} {d_m^{e}}} + q\bar{d}}}
\end{equation}

Donde $E$ representa al conjunto de los puntos extremos del frente de Pareto, y $d_m^{e}$ es la distancia del
 punto más cercano al extremo $e$, respecto de la función objetivo $m$. Se toma como $d_x$ la distancia
 euclidiana desde el punto $x$ a su vecino más cercano, siendo $\bar{d}$  el valor promedio de $d_x$ para 
 todas las soluciones en $PF_{known}$.

\paragraph{Speedup} Compara el tiempo medio de ejecución del algoritmo utilizando un solo procesador ($T_1$)
 contra el uso de $m$ procesadores ($T_m$), de forma tal de medir la mejora en el tiempo de ejecución
 obtenida al utilizar procesadores adicionales . Esta medida se refiere a la eficiencia en el uso del
 poder de cómputo en un ambiente en donde se interactúa con dos o más procesadores, se dice que el $speedup$ es
 lineal si al utilizar $m$ procesadores su valor es igual a $m$, sublineal si es menor que $m$ y es  superlineal
 cuando lo supera. {\it Speedup} se calcula mediante la siguiente expresión \ref{equation:speedup}. 

\begin{equation}
\label{equation:speedup}
 speedup = {T_1 \over T_m}
\end{equation}


Frecuentemente para medir $speedup$ se realizan varias ejecuciones y se toma el promedio de las mismas ya que la 
 duración de una ejecución puede verse influida por factores externos al algoritmo. Por ejemplo, en
 implementaciones que hagan uso de la red, la carga de la misma es un elemento externo al algoritmo
 que afecta el tiempo de ejecución.  


\subsubsection{Problemas estándar}\label{standard-problems}
Para comparar MOEAs es deseable contar no solamente con índices que nos permitan medir el rendimiento, 
 además hacen falta que se elaboren problemas que exploren las dificultades del enfoque para la resolución de
 problemas multiobjetivo, de forma de fomentar avances en la investigación de MOEAs. 

Deb en 1999 \cite{deb99multiobjective} identificó varias características de los MOPs que causan dificultades a
 los MOEAs: 

\begin{enumerate}

\item La existencia de óptimos locales plantea dificultades a los MOEA, dado que para
 alcanzar los óptimos globales se deberá mantener diversidad en la población, puesto que para encontrar los
 óptimos se deberá explorar el espacio de soluciones mas allá de los óptimos locales encontrados. 

\item Ciertas características respecto al frente de Pareto afectan a los MOEA en su capacidad de encontrar 
 soluciones óptimas de Pareto: convexidad o concavidad, uniformidad y continuidad del frente de Pareto, cada una
 de estas características hacen que si un MOEA no mantiene un conjunto de soluciones no dominadas
 uniformemente distribuido no se muestree correctamente el frente de Pareto.

\end{enumerate}

En el año 2000 Zitzler, Deb y Thiele \cite{ZDT_2000}, construyeron una serie de problemas que explotan distintas
 combinaciones de los aspectos de los MOPs que causan dificultades a los MOEA, además
 introducen distintos tipos de codificaciones de individuos, para poner a prueba los
 operadores evolutivos y su interacción con los distintos algoritmos.

Cada uno de los problemas ZDT tiene la forma :

\begin{eqnarray*}
\quad \mbox{Minimizar }  F(x) &=& [f_1(x_1), f_2(x)] \\
\quad \mbox{sujeto a } f_2(x) &=& g(x_1, \dots, x_m) h(f_1(x_1), g(x_2, \dots, x_m)) \\
\quad \mbox{donde }  x &=& (x1, \dots, x_m)
\end{eqnarray*}

La función $f_1$ depende solamente de la primer variable de decisión, $g$ es una función de las restantes $m-1$
 variables y los parámetros de $h$ son los valores de las funciones $f_1$ y $g$. Los problemas que los autores
 plantean se diferencian en esas tres funciones así como también en el número de variables $m$ y los valores
 que ellas pueden tomar. A continuación se presentan las seis funciones que siguen este esquema.


\paragraph{ZDT1} 

\begin{eqnarray*}
f_1(x_1) &=& x_1 \\
g(x_2, \dots, x_m) &=& 1 + 9 \displaystyle\sum_{i=2}^{m} {x_i\over{m - 1}} \\
h(f_1, g) &=& 1 - \sqrt{f_1 \over g} \\
\end{eqnarray*}

donde $m = 30$, y $x_i \in [0,1]$, el frente de Pareto real se encuentra en las soluciones
que hacen $g(x) = 1$, \textit{ZDT1} presenta un frente de Pareto convexo y continuo

\paragraph{ZDT2}

\begin{eqnarray*}
f_1(x_1) &=& x_1 \\
g(x_2, \dots, x_m) &=& 1 + 9 \displaystyle\sum_{i=2}^{m} {x_i\over{m - 1}} \\
h(f_1, g) &=& 1 - {\left(f_1 \over g \right)}^2 \\
\end{eqnarray*}

donde $m = 30$, y $x_i \in [0,1]$, el frente de Pareto real se encuentra en las soluciones
que hacen $g(x) = 1$, este problema es la contraparte cóncava a \textit{ZDT1}


\paragraph{ZDT3}

\begin{eqnarray*}
f_1(x_1) &=& x_1 \\
g(x_2, \dots, x_m) &=& 1 + 9 \displaystyle\sum_{i=2}^{m} {x_i\over{m - 1}} \\
h(f_1, g) &=& 1 - \sqrt{f_1 \over g} - {\left( f_1 \over g \right) } \sin(10\pi f_1) \\
\end{eqnarray*}

donde $m = 30$, y $x_i \in [0,1]$, el frente de Pareto real se encuentra en las soluciones
que hacen $g(x) = 1$, la introducción de la función $sin$, produce discontinuidad periódica a lo largo
del frente, sin embargo no hay discontinuidad en el espacio de soluciones.

\paragraph{ZDT4}

\begin{eqnarray*}
f_1(x_1) &=& x_1 \\
g(x_2, \dots, x_m) &=& 1 + 10(m -1) + \displaystyle\sum_{i=2}^{m} {(x_i^2 - 10 \cos(4 \pi x_i))} \\
h(f_1, g) &=& 1 - \sqrt{f_1 \over g} \\
\end{eqnarray*}

donde $m = 10$, $x_i \in [0,1]$ y $x_2, \dots , x_m \in [-5, 5]$, el frente de Pareto real se encuentra en las soluciones
que hacen $g(x) = 1$. Este problema presenta $21^9$ frentes de Pareto locales, poniendo a prueba la habilidad de los algoritmos
de mantener diversidad en la población.

\paragraph{ZDT5}

\begin{eqnarray*}
f_1(x_1) &=& 1 + u(x_1) \\
g(x_2, \dots, x_m) &=& \displaystyle\sum_{i=2}^{m} {v(u(x_i))} \\
h(f_1, g) &=& 1 \over f_1\\
\end{eqnarray*}

donde las soluciones se codifican como un {\it string} de bits, $m = 10$, $x_i \in {\lbrace 0,1 \rbrace}^30$, $x_2, \dots , x_m \in {\lbrace 0,1 \rbrace}^5$ y
$u(x_i)$ retorna la cantidad de unos del vector $x_i$ y además

\begin{eqnarray*}
v(u(x_i)) = &   2 + u(x_i) & \mbox{ si } u(x_i) < 5 \\ & 1 & \mbox{ si } u(x_i) = 5 
\end{eqnarray*}

El frente de Pareto, se encuentra cuando $g(x) = 10$, mientras que el mejor frente se ubica en $g(x) = 11$. Los
 frentes locales y óptimos son todos convexos.

\paragraph{ZDT6}

\begin{eqnarray*}
f_1(x_1) &=& 1 - e^{-4x_1}\sin^6(6\pi x_1) \\
g(x_2, \dots, x_m) &=& 1 + 9\left( {{ \displaystyle\sum_{i=2}^{m} {x_i}} \over  {m - 1}} \right) ^{1 \over 4} \\
h(f_1, g) &=& 1 - \left(f_1 \over g \right)^2\\
\end{eqnarray*}

donde $m=10$, $x_i \in [0,1]$. El frente de Pareto real se forma sobre $g(x) = 1$ y es cóncavo. Este problema
 plantea dos dificultades por la no uniformidad del espacio de búsqueda: las soluciones, no están distribuidas 
 uniformemente a lo largo del frente de Pareto (el frente está sesgado a soluciones en las que $f_1(x)$ es
 cercano a uno) y la densidad de soluciones en el espacio de búsqueda cerca del frente de Pareto es menor que en
 puntos alejados del mismo.


%\begin{figure}[h]
%\centering
%\includegraphics[scale=0.3]{graphs/ZDT/ZDT1_plot.png}
%\includegraphics[scale=0.3]{graphs/ZDT/ZDT2_plot.png}
%\includegraphics[scale=0.3]{graphs/ZDT/ZDT3_plot.png}
%\includegraphics[scale=0.3]{graphs/ZDT/ZDT4_plot.png}
%\includegraphics[scale=0.3]{graphs/ZDT/ZDT5_plot.png}
%\includegraphics[scale=0.3]{graphs/ZDT/ZDT6_plot.png}

%\caption{Frentes de Pareto de los problemas ZDT}\label{fig:ZDT}
%\end{figure}

\section{Resumen}
En este capítulo se presenta a grandes rasgos a la computación evolutiva como técnica para resolver MOP,
 se expusieron los orígenes de la teoría que aplica los principios evolucionistas, las tendencias actuales, la
influencia del paralelismo y las formas de comparación entre distintas aproximaciones a la resolución de MOP. 
En el siguiente capítulo se presenta una breve reseña de las implementaciones de MOEAs paralelos
y se entra en detalle en las que resultaron mas relevantes e influyentes en la implementación del {\it framework} 
que se presenta en el capítulo \ref{chapter::moe}.

\chapter{Paralelismo aplicado a MOEAs}\label{chapter::pmoea}

%El paralelismo se puede aplicar a los MOEA desde dos puntos de vista: para la resolución de un problema en particular o como parte de la creación de una biblioteca
%o {\it framework} de trabajo. La diferencia entre estas dos ópticas consiste en que la aplicación a problemas en particular
%tiene fines más prácticos. En la resolución de problemas particulares el paralelismo se utiliza para resolver problemas 
%de escalabilidad inherentes metodología de resolución utilizada. En el caso de la aplicación del paralelismo en bibliotecas o {\it frameworks} 
%espera resolver los problemas de escalabilidad antes que se presenten, además de aprovechar las ventajas de los AE paralelos en general (ver sección \ref{PEA}).

Existen distintas compilaciones que resumen la investigación y aplicación del paralelismo a los EA en general y
a los MOEA en particular, en \cite{alander96indexed, Coello_Coello_MOEA} se puede apreciar el incremento
en la investigación en el área, así como la aparición en el último tiempo de aplicaciones de 
MOEAs paralelos a la resolución de MOPs.
 Sin embargo, no son frecuentes los desarrollos de bibliotecas o {\it frameworks} especializados en el área.

En las secciones siguientes se describen brevemente algunas referencias de trabajos en el área, así como también se detallarán
algunos proyectos relevantes; que en conjunto permiten
apreciar el potencial que tiene la aplicación del paralelismo a los MOEAs.

\section{Trabajos relacionados}

\subsection{A Parallel Genetic Algorithm For Multiobjective Microprocessor Design}
        En 1995 Stanley y Mudge \cite{stanley95parallel} propusieron un algoritmo genético paralelo multiobjetivo aplicado al problema de diseño
        de procesadores. El problema del diseño de procesadores implica la creación de una estructura compuesta de varias piezas
        de hardware que interactúan entre sí, donde los componentes están restringidos en espacio físico dentro del procesador, 
        y también están restringidos desde el punto de vista de la disipación del calor. Además toda la estructura del procesador tiene
        restricciones de presupuesto. La complejidad de las combinaciones a las que se enfrenta el diseñador se ve aumentada
        por la alta exigencia en términos de poder de cómputo que tiene la evaluación de un diseño propuesto. A medida que se mejora
        la tecnología aumentan también la cantidad de posibles componentes de un procesador, por lo que el problema es cada vez
        más difícil de resolver. Sin embargo, el mercado demanda ciclos de diseño cada vez más cortos. La resolución del problema se plantea
        como un problema de optimización multiobjetivo, donde los objetivos representan las restricciones de espacio, disipación
        de calor y de presupuesto monetario. Para resolver el problema los autores proponen la utilización de un algoritmo evolutivo
        basado en MOGA modificado para delegar la evaluación de los diseños a computadores conectados a través de internet. 
        El modelo de paralelismo utilizado en el algoritmo propuesto está basado en el modelo de grano grueso, las restricciones en 
        el uso del hardware que tuvieron los autores hizo que implementaran la solución de forma que las evaluaciones en los esclavos
        se ejecutaran solamente cuando el computador estuviera libre. Lamentablemente los
        autores no incluyeron resultados que muestren las mejoras en el uso del poder de cómputo disponible.

\subsection{Aeorodynamic and Aeroacoustic Optimization Of Airfoils Via A Parallel Genetic Algorithm}
        Jones, Crossley y Lyrintzis propusieron en 1998 \cite{jones98aerodynamic} un algoritmo genético paralelo usado 
        para generar en un sola ejecución una familia de diseños de alas que sean eficientes desde el punto de vista aerodinámico 
        y produzcan el menor sonido posible al ser utilizadas. Se plantea el problema de diseño de alas como un problema
        de optimización multiobjetivo, identificando varias variables de control que determinan el diseño final. 
        Los objetivos del MOP son maximizar los coeficientes aerodinámicos y acústicos. La metodología de resolución está basada en un algoritmo genético en el que 
        para alcanzar el frente de Pareto se utilizó un operador de selección basado en torneo que favorece a los individuos dominantes. 
        Para la evaluación de los diseños se utilizaron análisis específicos para las dos dimensiones del problema. Dado que estos análisis son costosos en poder 
        de cómputo se delegaron a otros computadores, de modo de paralelizar con el modelo de grano grueso la ejecución del algoritmo. Para resolver la comunicación entre procesos se utilizo
        MPI ({\it Message Passing Interface} \cite{Gropp:1994:UMP}), durante los experimentos se utilizaron 8, 16, 32 y 64 nodos reportándose medidas de {\it speedup}
        lineales y obteniéndose resultados de calidad similar a los obtenidos con la versión serial del algoritmo.

\subsection{A Multiobjective Genetic Algorithm for Radio Network Optimization}
        Meunier, Talbi y Reininger en 2000 \cite{Meunier00} resolvieron el diseño de una red para telefonía celular utilizando un MOEA paralelo.

        El problema de diseño de una red de telefonía celular consiste en la ubicación de un número 
        de radiobases y su posterior configuración en un conjunto de lugares preseleccionados. Las radiobases administrarán la red en cierto rango de acción, además la distribución de estas radiobases
        debe complacer los siguientes objetivos: minimizar el número de radio bases, maximizar la capacidad de tráfico en la red y minimizar las interferencias
        entre los radios de acción de las radiobases, este objetivo esta vinculado directamente a la asignación de frecuencias a las radiobases puesto que 
        cuanto menos se solapen los radios de acción de las radiobases más sencilla será la asignación de frecuencias. 
        
        Se propone para resolver este MOP utilizar un MOEA basado en MOGA,
        en el que se asigna {\it fitness} de acuerdo a lo propuesto por Fonseca y Flemming en \cite{fonseca95overview} e incorpora {\it fitness sharing} como estrategia para
        mantener la diversidad. El paralelismo en este algoritmo sigue el modelo de grano grueso, puesto que se delega la evaluación de las funciones objetivo a los esclavos.
        Las ejecuciones para obtener resultados se efectuaron en una red de 24 nodos y la comunicación se implementó a través de PVM 
        ({\it Parallel Virtual Machine} \cite{pvm_book, sunderam90pvm}). En el artículo no se reportan
        medidas de eficiencia respecto a {\it speedup}.


\subsection{The New Model of Parallel Genetic Algorithm in Multi-Objective Optimization Problems: Divide Range Multiobjective Genetic Algorithm (DRMOGA)}
    Hiroyasu, Miki y Watanabe \cite{Hiroyasu00} proposieron  en el año 2000 un nuevo modelo de algoritmos genéticos paralelos para resolver 
    MOPs, al que llamaron {\it Divide Range Multiobjective Genetic Algorithm}. 

    En DRMOGA la población del GA es ordenada
    respecto a los valores de las funciones objetivo y dividido en subpoblaciones. En cada una de las subpoblaciones se utiliza
    un MOEA. Con una determinada frecuencia (en generaciones), todos los individuos son reagrupados en una sola población y ordenados nuevamente. 
    En este modelo, las soluciones óptimas de Pareto que son cercanas, se agrupan en una misma subpoblación, debido a que tienen valores
    cercanos en las funciones objetivo. Esto permite DRMOGA buscar en el vecindario de las soluciones óptimas de Pareto con mayor
    eficiencia.
    
    A través de Los autores demuestran la capacidad del algoritmo de alcanzar el frente de Pareto en MOPs de prueba estándar \cite{deb99multiobjective, vanveldhuizen99multiobjective}
    inclusive en problemas multimodales, mejorando los resultados del modelo de islas clásico, aunque no 
    se muestran medidas de {\it speedup} en el artículo.
            
\subsection{Pump Scheduling Optimization Using Asynchronous Parallel Evolutionary Algorithms}
   En 2004 Lücken, Barán y Sotelo  \cite{Lucken2004} propusieron utilizar MOEAs paralelos para resolver
    el problema de optimizar la programación del bombeo de agua. Optimizar la programación del bombeo de agua es relevante
    para la reducción de costos en la distribución de estaciones de bombeo. A medida que la red de estaciones de bombeo crece,
    el problema de la programación del bombeo se convierte en una tarea complicada.     
    En el artículo los autores proponen utilizar 
    MOEAs paralelos con migración asincrónica como herramienta para alcanzar la programación óptima del bombeo. En este contexto
    una programación óptima tomará en cuenta cuatro objetivos: costo en energía eléctrica, costo de mantenimiento, pico máximo 
    de potencia y el nivel de variación de la reserva. En el artículo se ensayan diversos MOEA paralelos y secuenciales. Los
    análisis de los resultados para las diferentes implementaciones muestran que las versiones paralelas asincrónicas son superiores
    en cuanto a la calidad de los resultados encontrados.

\subsection{MRMOGA: Parallel Evolutionary Multiobjective Optimization using Multiple Resolutions}
    En 2005 Jaimes y Coello  \cite{Lopez05a} propusieron un nuevo modelo de paralelismo para MOEA basado en 
    el modelo de islas con nodos he\-te\-ro\-gé\-neos. El algoritmo se caracteriza por codificar las soluciones usando 
    diferentes niveles de resolución por cada isla, dividiendo de esta manera el espacio de búsqueda en regiones solapadas. 
    Las regiones están organizadas jerárquicamente de forma que la región de mas alto nivel tiene el mayor nivel de precisión
    en la codificación de las variables. Cada isla ejecuta un MOEA serial que es inicializado de manera aleatoria. Durante la 
    migración cada proceso toma algunos individuos del frente de Pareto encontrado al momento y los envía a la población de
    sus vecinos, que potencialmente aumentan la precisión de la codificación. Al final de la ejecución el proceso de más
    alta jerarquía combina los frentes de Pareto encontrados por cada isla. La propuesta está basada en la premisa de que el
    frente de Pareto se encuentra en pocas iteraciones usando una co\-di\-fi\-ca\-ción de precisión baja debido a que el espacio de 
    búsqueda es menor. 

Las reseñas presentadas anteriormente muestran el interés de la comunidad académica en los MOEAs paralelos 
y sus aplicaciones. En la sección
 siguiente se analizarán en profundidad algunas implementaciones de MOEAs paralelos.

\section{Implementaciones}

Además de las referencias de investigación resumidas en la sección previa, existen 
 bibliotecas
o {\it frameworks} para MOEAs y MOEAs paralelos que han sido de vital importancia para el avance en el área. A continuación presentan 
detalles de algunas implementaciones que sirvieron de inspiración -tanto por su diseño como por los conceptos que
utilizan-, para la elaboración del {\it framework} que se presenta en el capítulo siguiente. Para todas estas implementaciones
se realizó un análisis exhaustivo del código fuente y de la documentación disponible con el objetivo de analizar en profundidad las propuestas de diseño de MOEAs paralelos


\subsection{PNSGA-II}

En su trabajo de 2004, Nesmachnow \cite{Nesmachnow_2004} propuso una versión paralela del MOEA NSGA-II y su aplicación al diseño de redes de comunicaciones
confiables. La versión paralela introduce cambios en el diseño e implementación de la versión original de Deb (2000) \cite{Deb_2000} orientadas
a la paralelización del algoritmo utilizando el modelo de islas. En el trabajo se analiza la versión modificada evaluando la calidad 
de los resultados con las métricas estándar: cantidad de puntos no dominados, {\it spread}, {\it spacing}, distancia generacional y {\it speedup}; y comparándolas
con la versión serial del algoritmo. Para tomar las medidas se utilizó un conjunto  de problemas estándar: los problemas ZDT \cite{ZDT_2000}, los problemas de Schaffer \cite{657079}, el problema de Kursawe \cite{kursawe91variant}, el problema simple con restricciones de Deb \cite{559152}, el problema de Binh y Korn \cite{binh97mobes} y los problemas de Viennet \cite{Viennet96}.
Además el autor incluye la aplicación del algoritmo obtenido al problema de diseñar una red de comunicaciones de mínimo costo que verifique requisitos prefijados de conexión 
entre pares de nodos de terminales. 


El transporte de las soluciones para el operador de migración fue construido en base a {\it MPI},
que consiste en un conjunto de interfases para el pasaje de mensajes entre procesos muy utilizado en computación de alto rendimiento. La topología
de la red de islas sigue el modelo de anillo unidireccional, es decir cada isla tiene un único canal de comunicación y están ordenadas en un
anillo. El operador de migración opera ascincrónicamente transportando los datos que representan a los individuos entre poblaciones.
Cada isla evoluciona dentro de un proceso independiente, por lo que la asincronía supone una mejora en eficacia en ambientes en que los procesos
presentan rendimientos he\-te\-ro\-gé\-neos.


Las modificaciones que Nesmachnow introduce en el diseño de NSGA-II se corresponden con la incorporación del operador
de migración y las políticas de emigración e inmigración. Esto altera el bucle principal de NSGA-II que se puede apreciar
en el algoritmo \ref{algorithm:NSGAII}. La incorporación del operador de migración se puede apreciar en el algoritmo \ref{algorithm:PNSGAII};
el bucle principal se altera cuando la condición de migración es verdadera, en ese caso se seleccionan los individuos
emigrantes, se produce la emigración, luego se incorporan los individuos inmigrantes si existieren. Dado que la comunicación es a\-sin\-cró\-ni\-ca 
podría no haber potencialmente individuos inmigrantes. La incorporación de las soluciones inmigrantes se realiza a través de la sustitución de los peores individuos
de la población actual.

\begin{algorithm}
\footnotesize
\caption{PNSGA-II}
\label{algorithm:PNSGAII}
\begin{algorithmic}
\STATE $Inicializar(P(0))$
\STATE $generacion = 0$
\STATE $Evaluar(P(0))$
\REPEAT
\STATE $R = Padres \cup Hijos$
\STATE $Frentes = Sorting No Dominado(R)$
\STATE $NuevaPop = \emptyset$
\STATE $i=1$
\WHILE{$|NuevaPop| + |Frentes(i)| <= sizepop$}
\STATE $Calcular Distancia De Crowding (Frentes(i))$
\ENDWHILE
\STATE $NuevaPop = NuevaPop \cup Frentes(i)$
\STATE $i = i+1$
\STATE $Sorting Por Distancia (Frentes(i))$
\STATE $NuevaPop = NuevaPop \cup Frentes(i)[1:(sizepop - |NuevaPop|)$
\STATE $Hijos = Seleccion Y Reproduccion(NuevaPop)$
\STATE $generacion = generacion+1$
\STATE $P(generacion) = NuevaPop$
\IF {$CondicionMigracion$}
\STATE $Emigrantes = SeleccionMigracion(P(generacion))$
\STATE $Inmigrantes = Migracion(Emigrantes)$
\STATE $Insertar(Inmigrantes, P(generacion))$
\ENDIF
\UNTIL{${CriterioParada}$}
\end{algorithmic}
\end{algorithm}


La evolución de cada subpoblación finaliza al alcanzar el criterio de parada. En
ese momento, cada isla envía la totalidad del frente de individuos no dominados de su población a una isla
distinguida que actúa como receptora de los individuos no dominados del resto de las islas. De ser necesario,
la isla receptora aumenta dinámicamente el tamaño de su población y aplica el proceso evolutivo durante un
pequeño número de generaciones extra, potenciando al algoritmo distribuido al operar solamente con las mejores soluciones
obtenidas en las islas. Este procedimiento permite mejorar la convergencia aumentando el número de puntos no dominados globales y también
mejorar la distribución de los individuos a lo largo del frente.

Del análisis de la ejecución de PNSGA-II sobre un amplio conjunto de problemas de prueba, se puede apreciar
una notoria mejora en el desempeño obtenido al
utilizar el algoritmo paralelo para resolver los problemas utilizando 4 procesadores. Se obtuvo un {\it speedup}
superlineal para todos los casos estudiados, salvo en los problemas ZDT1 y ZDT5 donde el comportamiento
observado correspondió a un {\it speedup} lineal. Estos resultados confirman la argumentación de Deb \cite{deb-distributed}
en su estudio sobre la estrategia de paralelismo por división de dominio aplicada sobre el algoritmo
NSGA-II, donde se reporta haber alcanzado valores de {\it speedup} superlineal.

Este proyecto no es solamente interesante desde el punto de vista práctico sino que también aporta ideas que son de vital importancia
en el diseño del {\it framework} que se presenta en el capítulo siguiente. Además, los resultados presentados sirven 
como puntos de referencia para contrastar los resultados obtenidos en este proyecto.

\subsection{DEME: DistributEd MEtaheuristics}

El proyecto DEME \cite{DEME} de la universidad de Málaga persigue el estudio de la resolución de problemas multiobjetivo
utilizando algoritmos metaheurísticos
secuenciales consolidándolos en un \textit{framework} que permite el análisis, investigación y aplicación de estos métodos
para resolver problemas del mundo real. También se brinda un entorno de pruebas para nuevos emprendimientos en el área,
a través de una \textit{API} clara y concisa que fomenta el reuso de los elementos comunes. 
La forma tradicional de aplicación de los MOEA a un problema implica una aproximación similar a la propuesta en PNSGAII:
dada una implementación de referencia, se la modifica para adaptarla al problema. Sin embargo, no es raro que
se pretenda resolver por varios caminos un problema, por lo que todo ese trabajo de adaptación se pierde de un enfoque a otro.
A su vez, a los investigadores se les ofrece un punto de partida bastante avanzado en lo que respecta a la implementación.


Se enumeran a continuación los objetivos que persigue DEME.

\begin{itemize}

\item Diseño e implementación de una biblioteca de objetos para la construcción de metaheurísticas, en particular las basadas
en poblaciones, como es el caso de los AE. Para ello deberá incluir los objetos básicos: poblaciones e
individuos y herramientas para su modelado. Además para apoyar los proyectos se debe de proveer operadores de mutación,
cruce, migración, selección y otros.

\item Construir una biblioteca de problemas multiobjetivo, en los que será posible utilizar cualquier metaheurística, por lo que 
el modelado de los problemas no deberá depender de la forma de resolución.

\item Construir una biblioteca de algoritmos metaheurísticos que implemente las técnicas más conocidas. Las implementaciones
deberán de ser lo mas claras y fieles a las intenciones de los autores originales, de manera que sirva con fines tanto educativos como
prácticos.

\end{itemize}


\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-Dependencias-DEME.png}
\caption{Bibliotecas DEME}\label{fig:DEME bibliotecas}
\end{figure}

Lamentablemente DEME es un proyecto descontinuado (de acuerdo a \cite{DEME} la última modificación data de marzo del 2006). Sin embargo vale la pena analizarlo, dado que los objetivos coinciden
 en muchos casos con los de este proyecto. En la figura \ref{fig:DEME bibliotecas} se puede apreciar un diagrama de paquetes del proyecto DEME. 
La biblioteca {\it libmoea} permite modelar los individuos tanto de forma binaria, entera y real,
utilizando el mecanismo de herencia de objetos, permitiendo experimentar con distintas codificaciones
con los algoritmos implementados. La biblioteca {\it libmoea} 
es la que contiene los objetos base del {\it framework}, {\it libproblems} contiene los problemas, 
incluyendo a la familia de problemas ZDT \cite{ZDT_2000}, DTLZ \cite{deb02scalable} y otros.
La principal carencia de este proyecto es la ausencia del paralelismo, sugerencia de que fue
abandonado antes de completar ese objetivo.

\subsection{JMetal}

JMetal es un proyecto de la universidad de Málaga \cite{JMetal_project}, que persigue objetivos
similares a los de DEME y dado que comparten con el anterior algunos autores, se puede concluir que se trata
de la continuación del proyecto DEME. Los objetivos del proyecto JMetal como se resumen en el reporte técnico que lo define
\cite{JMetal} son:

\begin{itemize}

\item Simplicidad y facilidad de uso. Las clases provistas por JMetal siguen el principio de ortogonalidad, cada componente debe realizar
una sola cosa y hacerlo bien. Las clases base y sus operaciones deben ser intuitivas, y como consecuencia fáciles
de utilizar y entender. El \textit{framework} incluye implementaciones de varias metaheurísticas que se pueden usar como
puntos de partida para desarrollar nuevas técnicas.

\item Flexibilidad. Este objetivo un tanto vago y genérico se refiere entre otras cosas a que deberán existir mecanismos
sencillos para ejecutar los algoritmos con parámetros diferentes, incluyendo los específicos para cada técnica así como también
los relacionados con el problema a resolver. Considerando este objetivo, la composición de codificación, operadores y algoritmo
 necesaria para la resolución de un problema utilizando JMetal deberá ser configurable.

\item Portabilidad. Se posibilitará ejecutar las metaheurísticas en computadores con diferentes arquitecturas y plataformas,
para cumplir este objetivo la implementación se basa enteramente en \textit{Java}.

\item Capacidad de extensión. El \textit{framework} facilitará el agregado y modificación de problemas, operadores, algoritmos
y codificaciones, usando intensivamente herencia y enlazado tardío \cite{limberghen-building}.

\end{itemize}

En el reporte técnico de referencia \cite{JMetal}, los autores hacen hincapié en que todavía no se ha instaurado un ambiente homogéneo para el desarrollo, investigación
y comparación de metaheurísticas. Se plantea una situación en la que se comparan distintas implementaciones de algoritmos en ambientes
diferentes con rendimientos muy dispares. De esta manera, un objetivo no planteado en la lista anterior es el de obtener implementaciones
lo más fieles posibles a las de referencia, de forma de tener un entorno de trabajo que permita la comparación cuantitativa y cualitativa de
las técnicas presentes y futuras.

El {\it framework} desarrollado en este proyecto, que se presentará en el capítulo siguiente, converge en muchos de los objetivos de JMetal. 
Sin embargo,  se decidió tomar un camino diferente al de \textit{Java}, tratando de evitar las penalizaciones en el uso del poder de cómputo y 
 memoria de programas {\it Java} que afecta el desempeño computacional, en especial en aplicaciones complejas. 
Mientras se respeten los estándares \textit{ANSI} un programa escrito en \textit{C++} es tanto o más portable que el mismo programa escrito en
 {\it Java}. Esta afirmación se respalda en la comparación del amplio número de plataformas en las que existe un compilador \textit{ANSI C++}
 contra la cantidad de plataformas en las que existe una máquina virtual \textit{Java}.


\subsection{Mallba}\label{section:Mallba}

Mallba es un proyecto conjunto de las universidades de Málaga, La Laguna y Politécnica de Catalunya cuyo objetivo principal,
es el diseño e implementación de una biblioteca de esqueletos de algoritmos para la resolución de problemas de optimización.
Se define como esqueleto una herramienta genérica que permite la definición concreta de un problema de optimización a través
de la creación de instancias del método general de optimización que implementa. Mallba ofrece tres métodos para la resolución
de problemas: métodos exactos, heurísticas y métodos híbridos. La biblioteca ofrece además tres implementaciones de cada técnica:
secuencial, distribuido local (dentro de una LAN) y geográficamente distribuidos (en una WAN) \cite{optimization-mallba}.

La biblioteca ofrece a los usuarios una interfaz única para cada esqueleto independiente de la plataforma. El usuario final
solamente elige uno de los tres métodos de resolución y particulariza el esqueleto con las características del problema a resolver,
sin necesidad de tomar en cuenta los problemas relacionados con el método de distribución en sí mismo. Al final, el usuario dispondrá de 
tres instancias que resuelven el problema: una secuencial, una paralela para ejecución en red local y paralela para ejecución en una red de área global. Desde el punto de vista práctico, 
 el usuario deberá modificar el esqueleto de la técnica que decidió utilizar, implementando distintos aspectos particulares de la técnica
(por ejemplo, si se desea utilizar un algoritmo genético simple se debe implementar: la codificación, la función de {\it fitness}, y
los operadores de cruce y mutación).

Desde el punto de vista de la eficiencia computacional, Mallba tiene la principal ventaja de estar orientada al procesamiento paralelo. La distribución en LAN y en WAN
permite el uso de poder de cómputo remoto, implicando un avance para la investigación y desarrollo de estas técnicas. Como consecuencia de la orientación hacia el paralelismo, una de las partes que mas se destaca es el módulo de comunicaciones de la biblioteca. Los esqueletos disponibles paralelizan con el enfoque
de islas, al igual que PNSGAII. Es posible definir la topología
de interconexión entre islas, aunque en general la interconexión está implementada por defecto en forma de anillo unidireccional para los esqueletos disponibles.

Uno de las principales desventajas de Mallba es la ausencia casi total de documentación técnica del \textit{framework}.
El proyecto de grado ``Algoritmos Genéticos Incrementales'' \cite{Dominioni_2004} se realizó sobre Mallba, debido a esto realizando
 un trabajo de ingeniería reversa sobre el mismo cuyo resultado es la documentación de los mecanismos que utiliza Mallba.

En Mallba se distinguen tres tipos de clases:

\begin{description}

\item[Provistas] Son las clases, que modelan el método de resolución, dado que Mallba apunta a la resolución genérica de 
problemas de optimización se pueden encontrar: {\it Simulated Annealing}, GA, ES, {\it Ant Colony Optimization}, {\it Cooperative Local Search},
{\it Particle Swarm Optimization}, CHC y técnicas híbridas.

\item[Requeridas] Modelan el problema al que se aplica la técnica seleccionada, son las clases que el usuario deberá implementar
para utilizar Mallba.

\item[Internas] Necesarias para el \textit{middleware} de la biblioteca, utilitarios, etc.

\end{description}

A continuación se hace un análisis de cada uno de los tipos de clases para el caso particular del GA que se provee con la biblioteca.

\subsubsection{Clases Requeridas}

En la figura \ref{fig:clases-required-Mallba} se puede observar un esquema de alto nivel de las clases, que deberán ser
modificadas o implementadas al momento de instanciar la biblioteca. Para su uso se deben de proveer 
implementaciones de las clases {\tt Solution} y {\tt Problem} (marcadas con el estereotipo ``Required'').

\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-required-Mallba.png}
\caption{Clases Requeridas en Mallba}\label{fig:clases-required-Mallba}
\end{figure}
\clearpage


Refinando el análisis de la clase {\tt Solution}, en la figura \ref{mallba:Solution} se muestra su definición para el caso
en que se utilice una codificación real de los individuos. En el método {\tt fitness} se deberá
retornar el valor de {\it fitness} del individuo involucrado. Dado que en el ejemplo se trata del esqueleto de un GA, la función de {\it fitness}
coincidirá con la función objetivo del problema.

\begin{figure}[h]
\footnotesize
\begin{verbatim}
requires class Solution
{
public:
    Solution (const Problem& pbm);
    Solution (const Solution& sol);
    ~Solution();

    friend ostream& operator<< (ostream& os, const Solution& sol);
    friend istream& operator>> (istream& is, Solution& sol);
    friend NetStream& operator << (NetStream& ns, const Solution& sol);
    friend NetStream& operator >> (NetStream& ns, Solution& sol);

    const Problem& pbm() const;

    Solution& operator=  (const Solution& sol);
    bool operator== (const Solution& sol) const;
    bool operator!= (const Solution& sol) const;

    char *to_String() const;
    void to_Solution(char *_cadena_);

    void initialize();
    double fitness ();
    unsigned int size() const;

    float& var(const int index);
    Rarray<float>& array_var();

private:
    Rarray<float> _var;
    const Problem& _pbm;
};

\end{verbatim}
\caption{Definición de la clase {\tt Solution} de Mallba}\label{mallba:Solution}
\end{figure}

Un aspecto interesante de la definición
es la relación de {\tt Solution} con {\tt NetStream}, el objeto que representa la capa de comunicación de Mallba.
{\tt NetStream} es un {\it wrapper} de {\it MPI} que le da a este último una interfaz de flujo similar a las clases {\tt iostream} de la
biblioteca estándar de {\it C++}, permitiendo que el transporte de soluciones sea a la vez elegante y poderoso. La figura \ref{mallba:Solution:flujo} muestra la implementación de los operadores que permiten el transporte de soluciones utilizando {\tt NetStream}. 
La implementación de {\tt NetStream} está basada en {\it mpich} 1.2.7 \footnote{http://www.mcs.anl.gov/mpi/mpich1/ liberado el 4 de noviembre de 2005}
permitiendo a Mallba brindar distribución de procesos tanto en un ambiente local, global e inclusive sobre un multiprocesador utilizando las posibilidades
de memoria compartida de {\it mpich}.  

\begin{figure}
\footnotesize
\begin{verbatim}

NetStream& operator<< (NetStream& ns, const Solution& sol)
{
    for (int i=0;i<sol._var.size();i++)
        ns << sol._var[i];
    return ns;
}

NetStream& operator>> (NetStream& ns, Solution& sol)
{
    for (int i=0;i<sol._var.size();i++)
        ns >> sol._var[i];
    return ns;
}

\end{verbatim}
\caption{Implementación de los operadores de flujo de {\tt NetStream} en {\tt Solution}.}\label{mallba:Solution:flujo}
\end{figure}


Mallba permite la incorporación de estadísticas por parte del usuario de una manera sencilla. 
Existe un objeto llamado {\tt UserStatistics} que es un {\it observer}
de la clase {\tt Solver} que permite que se acumulen datos del más variado tipo.
Esto implica que al momento de particularizar las estadísticas, el usuario solamente deberá implementar el método {\tt update}
y hacer acuso de los cambios sobre el objeto de clase {\tt Solver} que mantiene datos referentes al estado del sistema.
\clearpage
Existen mecanismos para incorporar  operadores genéticos, representados en Mallba por las clases
{\tt Mutation} y {\tt Crossover} que deben conocer la representación interna de la clase {\tt Solution} puesto que operaran sobre esos datos.
Mallba modela esos operadores como clases heredadas de {\tt Intra\_Operator}, en clara referencia a que operan dentro
de cada población. Análogamente existe el objeto {\tt Inter\_Operator} cuya mecánica funciona entre poblaciones, siendo el ejemplo
más evidente es el operador de migración, aunque existen otros operadores considerando la amplitud del espectro de técnicas implementadas.




La clase {\tt Problem} consiste en la definición del problema en los siguientes términos:

\begin{description}
\item[Dirección] Este atributo determina si si se maximiza o minimiza la función objetivo, es decir cual es la dirección de
la optimización.
\item[Dimensión] Semánticamente se trata de la cantidad de variables involucradas en la codificación de los individuos.
\item[Restricciones] Se corresponden con las restricciones del problema de optimización, en el caso de Mallba se permite modelar 
los valores máximos y mínimos que tomarán cada una de las variables de decisión.
\end{description}



\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-provided-Mallba.png}
\caption{Clases {\it Provided} de Mallba}\label{fig:clases-provided-Mallba}
\end{figure}

\subsubsection{Clases Provistas}

En la figura \ref{fig:clases-provided-Mallba} se presentan las clases provistas por el esqueleto del GA, que articulan la
técnica que utilizada. La definición de interfaces de Mallba \cite{interfaces_mallba}
determina que el punto de entrada del algoritmo debe respetar la forma de la figura \ref{mallba:entry:point}.

\begin{figure}
\footnotesize
\begin{verbatim}
int main (int argc, char** argv){
    using skeleton newGA;

    ...
    Problem pbm;
    f2 >> pbm;

    Operator_Pool pool(pbm);
    SetUpParams cfg(pool);
    f1 >> cfg;

    Solver_Seq solver(pbm,cfg);
    solver.run();

    if (solver.pid()==0) {
        solver.show_state();
        cout << "Solution: " << solver.global_best_solution()
             << " Fitness: " << solver.global_best_solution().fitness() << endl;
        ...
        fexit << solver.userstatistics();
    }
    ...
}
\end{verbatim}
\caption{Punto de entrada de un esqueleto Mallba {\it MainSeq.cc}}\label{mallba:entry:point}
\end{figure}


En la función {\tt main} del punto de entrada del esqueleto Mallba se carga de archivo la configuración del problema, para
inmediatamente pasar el control al objeto {\tt Solver} que contiene la lógica del GA. El objeto {\tt Solver} utiliza
 al objeto {\tt Population} que es responsable de proveer la interacción entre los individuos basada en los operadores genéticos que producen la evolución de la población. La variación del código de la figura \ref{mallba:entry:point} en el caso del {\tt Solver} paralelo
es que se incorpora al objeto de la clase {\tt OperatorPool} el operador de migración, para intercambiar los individuos entre subpoblaciones.

De esta manera, Mallba permite con poco esfuerzo resolver problemas complejos utilizando técnicas evolutivas.
Sin embargo, el hecho de tener que modificar código fuente del esqueleto no es una interfaz flexible ni cómoda para la incorporación
de nuevos elementos. Al margen de  este problema de flexibilidad, cada esqueleto de Mallba es totalmente independiente, limitando  el
reuso de código a copiar código de un esqueleto similar si se desea hallar una solución con otro algoritmo.

El código de la mayoría de los esqueletos está concentrado en pocos archivos, con una modularización muy
pobre. De hecho, todos los objetos se definen en un único archivo de cabezales y luego las implementaciones se distinguen
solamente entre las clases provistas y requeridas, lo que no es una interfaz cómoda para su uso.

\clearpage
\section{Resumen}
Se presentaron en este capítulo distintas implementaciones de paralelismo en algoritmos evolutivos para optimización multiobjetivo, 
aplicaciones centradas
en la resolución de un problema en particular y varios entornos de trabajo y bibliotecas genéricas que permiten el uso
de AE paralelos para resolver problemas de optimización. Se analizó la implementación y diseño de cuatro proyectos de AE paralelos:
PNSGAII como ejemplo de aplicación particular y DEME, JMetal y Mallba como {\it frameworks}. De las implementaciones y referencias presentadas se han
extraído  los conceptos principales para posibilitar el diseño e implementación del MOE {\it framework}, que se presenta en el capítulo siguiente.

\chapter{MOE \it{Framework}}\label{chapter::moe}

El {\it framework} de MOEAs paralelos MOE surge como consecuencia lógica de los conceptos expuestos en los capítulos anteriores. Las
motivaciones de su creación son consolidar el conocimiento adquirido y servir como plataforma para futuros proyectos en el área.

\section{Objetivos}

El público para el que está pensado MOE comprende a todos aquellos que deseen conocer, enseñar, experimentar o utilizar MOEAs.
Se hace especial hincapié en la incorporación de paralelismo a los MOEAs, no solamente para mejorar el rendimiento
computacional sino también para mejorar la calidad de las soluciones.

Para garantizar que esta solución abarque a los posibles interesados, se hizo todo lo posible por alcanzar los objetivos que se
listan inmediatamente:

\begin{description}

\item[{\sc simplicidad}] Todo el proyecto intenta presentar una solución a la problemática planteada, minimizando
el impacto de la complejidad de la tarea en sí. Este objetivo se alcanza utilizando de manera sutil y coherente
las herramientas de las que se dispone. Desde la documentación hasta el diseño siempre se intentó seguir el camino
más sencillo y predecible. Una vista del diseño demuestra que este {\it framework} es lo 
suficientemente sencillo como para ser usado por el amplio espectro del público objetivo.

\item[{\sc flexibilidad}] El {\it framework} presenta desde el diseño la capacidad de estar preparado para el cambio.
Tomando en cuenta este aspecto las funcionalidades son claramente identificables y modulares, con una intromisión
mínima entre ellas lo que hace que la arquitectura resultante es simple, y por tanto correctamente preparada
para que sean retiradas, agregadas o modificadas la mayoría de las funcionalidades del sistema. MOE incluye ciertas capacidades
``extra'', las estadísticas, la bitácora y la presentación en general al usuario, que son elementos que no
interfieren con el uso del sistema.

\item[{\sc ortogonalidad}] Todo el sistema está compuesto de elementos que siguen la filosofía {\it ``haz solo una cosa y hazlo
realmente bien''} \cite{the_art_of_unix_programming}. Esta idea implica que una acción sobre un objeto no propaga ni provoca efectos colaterales, 
es decir que no altera al sistema de una manera inesperada.

\item[{\sc performance}] Desde la selección de las herramientas utilizadas, el diseño y la implementación se intenta
aprovechar al máximo los recursos (ciclos de CPU, memoria y ancho de banda de la red de comunicaciones), para permitir que las aplicaciones que utilicen MOE sean utilizables con efectividad en problemas reales.

\end{description}

\section{Diseño}



El {\it framework} está constituido por tres paquetes principales, cuyas dependencias se muestran en la figura \ref{fig:paquetes-MOE},
y su descripción se presenta a continuación.

\begin{description}

\item[engine] Es el paquete que contiene las clases base del sistema que permiten el modelado de los problemas, soluciones y algoritmos 
y cubren las funcionalidades mínimas del sistema.

\item[algorithms] Consiste en las clases que implementan los algoritmos para resolver los problemas.

\item[problems] Implementan los elementos que definen los problemas: co\-di\-fi\-ca\-ción de las soluciones, operadores 
específicos para cada codificación, criterios de optimización y restricciones.

\end{description}

Las secciones siguientes presentan una descripción en profundidad para cada uno de los paquetes que componen MOE.

\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-moe-paquetes.png}
\caption{Paquetes que componen a MOE}\label{fig:paquetes-MOE}
\end{figure}

\subsection{Paquete {\it engine}}

Las clases principales del paquete {\it engine} se pueden ver en la figura \ref{fig:engine-core-MOE}.  Este conjunto de clases se compone
de forma de dar el mínimo soporte necesario para instanciar un MOEA, representar los individuos, los operadores y los problemas.

La clase {\tt MOEA} implementa el esqueleto de un algoritmo evolutivo multiobjetivo. Sus
responsabilidades son las de proveer los mecanismos mas básicos para librar de esa tarea a los que la extiendan. En {\tt MOEA} se implementan los
 mecanismos que tienen en común todos los MOEA: administración de los operadores evolutivos y de selección, condiciones de término y de migración, 
mantener el estado actual de la evolución para actualización de las estadísticas e históricos 
y el mantenimiento de la población. {\tt MOEA} es también responsable de proveer políticas
de {\it scheduling} de operadores similares a los del {\tt OperatorPool} de Mallba \cite{Dominioni_2004}.


\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-moe-engine-core.png}
\caption{Clases principales del paquete {\it engine}}\label{fig:engine-core-MOE}
\end{figure}
\clearpage

La idea básica de la clase {\tt MOEA} es que aquellos que especialicen la clase implementen solamente los métodos virtuales y permita
que a través de la lógica contenida en {\tt MOEA} se articule la solución. Es así que en la clase {\tt MOEA} se encuentra el bucle principal
de los algoritmos que se implementen y que toma la forma que puede apreciarse en la figura \ref{MOEA:Main-loop}. La implementación de las funciones
{\tt stopCondition}, {\tt generation} y  {\tt migrationCondition} está a cargo de los desarrolladores que extiendan la clase, como forma 
de simplificar la construcción de extensiones o modificaciones. 

\begin{figure}
\footnotesize
\begin{verbatim}
virtual void run() {

    initialize();

    while (!stopCondition()) {
        generation();
        generations++;

        if (migrationCondition()) migrate();

        notifyObservers(this);
    }

    finalize();
}
\end{verbatim}
\caption{MOEA: bucle principal}\label{MOEA:Main-loop}
\end{figure}



Dentro de las clases principales del paquete {\it engine} se encuentra la clase {\tt NetStream} que fue tomada directamente
del proyecto Mallba visto en la sección \ref{section:Mallba}. Esta clase es responsable de proveer las primitivas de comunicación.

El modelo de paralelismo elegido para MOE es el de grano fino, presentado en la sección \ref{section:modelodegranofino}. En 
el contexto de MOE la implementación se articula a través de la clase {\tt Migration} que se encarga de: la selección, el transporte y la emigración e inmigración de los individuos entre islas. Para llevar a cabo su tarea la clase {\tt Migration} se sirve del operador de selección 
y de {\tt NetStream} para efectivizar el transporte de soluciones y sincronizar las operaciones con otras islas. 

La clase {\tt Population} mantiene una colección de objetos {\tt Solution}, para facilitar el trabajo de la clase {\tt MOEA}, liberándola
a esta de la administración del conjunto de soluciones y de la aplicación de operadores a este conjunto.

\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-moe-engine-solution.png}
\caption{Clases del paquete engine, vista de {\tt Solution}.}\label{fig:engine-solution-MOE}
\end{figure}


La clase {\tt Solution} representa la clase base de todas las codificaciones de solución. Al igual que {\tt MOEA}, {\tt Solution} libera a los usuarios que pretendan extender
el sistema del peso de las tareas mecánicas. En {\tt Solution} reside el código para evaluar los distintos objetivos de la
optimización representados como instancias de la clase {\tt Objective}. También en {\tt Solution} se encuentra la lógica que permite normalizar las
 soluciones fuera de la región factible del MOP; para lograrlo interactúa con las instancias de la clase {\tt Restriction} que modelan las restricciones del problema. Las relaciones entre las clases {\tt Solution}, {\tt Objective} y {\tt Restriction} se puede ver en la figura \ref{fig:engine-solution-MOE}.

Un punto importante a destacar es que las especializaciones de {\tt Solution} deberán proveer mecanismos a través de la herencia 
para transportar una instancia usando la clase {\tt NetStream} al igual que en el caso de Mallba.
 
\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{images/Diagrama-moe-engine-extras.png}
\caption{Clases del paquete engine, vista de {\tt Statistics}, {\tt Historic} y {\tt StatisticsSink}}\label{fig:engine-extras-MOE}
\end{figure}


En la figura \ref{fig:engine-extras-MOE} se presentan las clases que implementan las estadísticas y el histórico de la evolución. 
A través del uso del patrón de diseño {\it observer}, se puede
apreciar la no intromisión de estas tareas en los quehaceres de {\tt MOEA}, porque la interacción entre los mismos es a través de notificaciones.
 Las estadísticas del sistema, así también
como el histórico que actúan como bitácora de las soluciones participantes en la evolución. Las clases {\tt Statistics} y {\tt Historic} son fácilmente activadas y
desactivadas, inclusive en tiempo de ejecución. 

En Mallba existe un proceso (en el sentido de {\it MPI}) que se
dedica exclusivamente a la recepción de las estadísticas, su consolidación y posterior presentación al usuario. En MOE
ese concepto es representado por {\tt StatisticsSink} que es un objeto activo independiente de las islas y que además utiliza
una instancia de MOEA para realizar, si así se lo configura, algunas ejecuciones del MOEA. Este mecanismo, conocido como interacción panmítica es utilizado en PNSGAII para mejorar la calidad de resultados aumentando el número de puntos dominados globales \cite{Nesmachnow_2004}.

\subsection{Paquete {\it algorithms}}

El paquete {\it algorithms} contiene las clases que implementen los {\tt MOEA} concretos. La implementación inicial de MOE incluye la implementación de 
{\tt NSGAII} \cite{Deb_2000} que se detalla en la sección \ref{subsection:NSGAII_revisitado}.

\subsection{Paquete {\it problems}}

En el paquete {\it problems} se  encuentran las clases que implementan codificaciones, operadores de mutación, cruce, migración y selección, además en este paquete se incluyen las clases que modelan los problemas ZDT. A continuación se detallan las clases disponibles en el paquete problems:

\begin{itemize}
\item Codificaciones de soluciones binarias y reales: {\tt Int\-Array\-So\-lu\-tion} y {\tt RealArraySolution}.
\item Operadores de mutación para ambas implementaciones: {\tt Per\-turb\-Mutation} y {\tt RealPerturbMutation}, que implementan la mutación de un cromosoma aleatorio en las codificaciones binarias y reales respectivamente. Además se incluye al operador Polinomial para soluciones codificadas como reales, utilizado por Deb en NSGA-II \cite{Deb_2000}.
\item Operadores de cruzamiento: {\tt SinglePointCrossover}, {\tt Dual\-Point\-Crossover} y {\tt SBX} definido en \cite{SBX}.
\item Operadores de selección: {\tt Roulette\-Wheel\-Selection} y {\tt Tour\-na\-ment\-Se\-lec\-tion}.
\item Las restricciones y objetivos de los problemas ZDT \cite{ZDT_2000}.
\item La implementación concreta del operador de migración con topología de anillo en la clase {\tt RingMigration}.
\end{itemize}


%Siguiendo la línea del capítulo anterior, es fácil ver que los proyectos que allí figuran, fueron una fuerte influencia en el 
%presente diseño, en particular {\it Mallba}. Anteriores encarnaciones de éste emprendimiento intentaron extender los 
%esqueletos del proyecto, su fracaso motivaron la implementación actual del mismo, en el que no sólo reusan algunas clases
%sino que además, decisiones de diseño se tomaron directamente del proyecto.

Como se puede apreciar el diseño de MOE se inspira en los trabajos expuestos en el capítulo anterior. En particular la modularización es muy similar a la de DEME/JMetal, siguiendo   
una aproximación sencilla y efectiva al modelado del dominio de 
los MOEA. La influencia del diseño de Mallba en MOE se manifiesta en: la interacción entre instancias del algoritmo y las relaciones entre {\tt MOEA}, las estadísticas y los operadores.

En la sección siguiente se detallan algunos aspectos de la implementación.



\section{Implementación}

El {\it framework} está implementado enteramente en {\it C++} y depende solamente de mpich (esta dependencia está dada por {\tt NetStream}).
Por este motivo MOE sería en principio
fácilmente portable a cualquier plataforma que soporte la biblioteca mpich, en particular cualquier sistema {\it UNIX}. Como consecuencia, 
la compilación y ejecución del {\it framework} se utilizan {\it scripts} y herramientas de  sistemas {\it UNIX}, como por ejemplo
{\it Makefile} y {\it bash}. 

Cada uno de los paquetes que se describieron está pensado para ser fácilmente utilizado como biblioteca externa para 
alguna aplicación que lo necesite. De hecho, los {\it scripts} de compilación generan las bibliotecas listas para ser enlazadas. 
La salida de esta prueba de concepto
usa la herramienta de cálculo numérico {\it Octave} \cite{Octave_project} para evaluar las métricas 
que evalúan los resultados de un MOEA, presentadas en la sección \ref{section:Metricas}.
Utilizando {\it Octave} se independiza el análisis de resultados del {\it framework}, de forma de favorecer su simplicidad.

Se definen dos tipos de estadísticas: dinámicas y estáticas. Las estadísticas dinámicas están implementadas a través de la clase {\tt Statistics},
 que representan las estadísticas en tiempo de ejecución, por defecto se soporta un contador de soluciones diferentes y el tamaño del frente encontrado
 al momento, el usuario que entienda que no son suficientes tiene la posibilidad de extenderlas. 
Las estadísticas estáticas se corresponden con el análisis a {\it posteriori} del resultado
de la ejecución, y quedan abiertas para que el usuario las construya. En el programa de prueba se utiliza {\it Octave} para realizar 
los cálculos de postprocesamiento, pero este hecho no constituye un requerimiento para el uso del sistema.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{images/Diagrama-deploy.png}
\caption{Diagrama de despliegue de la aplicación.}\label{fig:deploy-MOE}
\end{figure}

La interacción entre instancias en modo paralelo se implementó de dos modos: sincrónico y asincrónico. En el modo
 sincrónico, al cumplirse la condición de migración todas las islas se detienen
en un punto y en ese tiempo se produce el intercambio. El modo asincrónico no exige que las islas se 
detengan para llevar a cabo el intercambio. La elección entre uno u otro mecanismo de sincronización para la migración se deja al usuario. 

%En condiciones en que se espera que el proceso de evolución
%tenga la misma duración, conviene utilizar el método sincrónico, cuando entramos en ambientes mas heterogéneos, es más eficiente
%el uso asincrónico. Notar que no solamente depende de la heterogeneidad del poder de cómputo y la red, etc. están involucrados
%en ésta decisión los criterios de optimización, etc.

En la figura \ref{fig:deploy-MOE} se muestran las interacciones en una ejecución con tres islas,
 entre las que existe un intercambio de soluciones. A medida que se generan eventos, las estadísticas se dirigen
a {\tt StatisticsSink}, que  tiene como responsabilidad concentrar y consolidar la información, de forma de tener
una imagen centralizada del estado de la ejecución.

%Se intentó a lo largo de la implementación utilizar un subconjunto de las posibilidades de {\it C++} de forma que,
%la complejidad de la comprensión del código no escape y además ser lo mas eficiente, en el uso de los recursos computacionales,
%como sea posible. 

%Se uso {\it Doxygen} \footnote{www.doxygen.org/} para generar la documentación técnica de bajo nivel, ésta herramienta
%toma los comentarios (con cierto formato) en los fuentes y les da una interfaz web, ideal para su uso como referencia 
%o visualización de los componentes involucrados, se proveen de {\it scripts} para su uso de forma automática. 


Como prueba de concepto del {\it framework} se implementó el algoritmo NSGA-II \cite{Deb_2000}. Esta decisión esta basada en los
excelentes resultados que ha demostrado alcanzar este algoritmo \cite{Anile05, Hiroyasu05b, Kollat06}, lo que hace factible utilizar MOE en problemas reales. A continuación se detalla la implementación de NSGA-II en el marco 
de MOE.


\subsection{Revisión de NSGA-II}\label{subsection:NSGAII_revisitado}

La motivación de la creación de NSGA-II residió en las siguientes críticas sobre el NSGA original \cite{srinivas94multiobjective},
 presentadas en la sección \ref{section:NSGA}:

\begin{description}

\item{Uso ineficiente de los recursos} debido a la complejidad innecesaria de la función que ordena la población según dominación de 
Pareto. Este componente del algoritmo tenía en la versión original una complejidad $O(m N^3)$ (con $m$ la cantidad de objetivos y $N$ el tamaño de la población), provocando que el algoritmo en su totalidad
fuese poco eficiente. En NSGA-II el ordenamiento por dominancia tiene complejidad  $O(m N^2)$, como consecuencia de una mejora en el almacenamiento de resultados
y la recorrida de la población.

\item{Falta de elitismo}. Se demostró en el artículo de Zitzler \cite{Zitzler_SPEA} que el elitismo favorece significativamente 
la {\it performance} y además previene la perdida de soluciones óptimas de Pareto.

\item{Necesidad de especificar $\sigma_{share}$}. El mecanismo de preservación de diversidad en NSGA necesitaba 
este parámetro, agregando complejidad innecesaria. Utilizando otras técnicas para la diversidad se suprimió el uso de ese parámetro.

\end{description}

En el algoritmo \ref{algorithm:NSGAII} se muestra el pseudocódigo de NSGA-II que difiere en la práctica de NSGA en dos puntos:
la función que calcula los frentes existentes llamada {\it fast-nondominated-sort} y la función que consolida la siguiente población a través 
de la función {\it crowding-distance-assignment}. A con\-ti\-nua\-ción se detallan las implementaciones de estas dos funciones.


\subsubsection{Función {\it fast-nondominated-sort}} 

En NSGA-II, la función {\it fast-nondominated-sort} se encarga de ordenar la población según la cantidad
de individuos dominados, separándolos en conjuntos de soluciones con la misma cantidad de individuos dominados, (a estos conjuntos 
Deb los llama $F_i$, siendo $i$ la cantidad de individuos dominados). 
El mecanismo de esta función se puede apreciar en el algoritmo \ref{nsgaII::fast-nondominated-sort}. 

\begin{algorithm}
\footnotesize
\caption{{\it fast-nondominated-sort}}\label{nsgaII::fast-nondominated-sort}
\begin{algorithmic}
\STATE$F_i = IndividuosDominantes(P)$
\FORALL{$p \in P$}
\STATE $n_p = Cantidad De Individuos Que Dominan A p$
\STATE $S_p = Individuos Que p Domina$
\ENDFOR
\STATE$i = 1$
\WHILE{$F_i \neq \emptyset$}
\FORALL{$q \in S_p$}
\STATE$n_q = n_q - 1$
\IF {$n_q = 0$}
\STATE$H = H \cup q$
\ENDIF
\ENDFOR
\STATE $i = i + 1$
\STATE $F_i = H$
\ENDWHILE
\end{algorithmic}
\end{algorithm}

La función {\it fast-nondominated-sort} calcula por cada solución dos entidades: $n_i$, que representa la cantidad de soluciones que dominan al
individuo analizado y $S_i$, que es el conjunto de soluciones que el individuo domina. El cálculo de estas dos 
entidades requiere $O(mN^2)$ evaluaciones de dominación. 
%Después se identifican aquellos individuos que tengan
%$n_i = 0$ y se colocan en la primera lista que representa al %frente actual $F_1$. Luego, se recorre ésta lista y 
%para cada solución $q$ en  en el conjunto se reduce en $1$ el valor de $n_q$. de las soluciones en $S_j$ si alguno de estos 
%individuos $k$ alcanza por ello el valor $0$ en $n_k$ se lo coloca en una lista $H$. Cuando todos los individuos
%en el frente actual se procesaron, se repite el procedimiento utilizando a las nuevas soluciones identificadas
%en $H$. 

Cada una de las iteraciones del bucle final de {\it fast-nondominated-sort} requiere $O(N)$ comparaciones,
(el bucle continúa hasta que se hallan identificado
todos los $F_i$). Como la cantidad de conjuntos $F_i$ máxima es $N$ (cuando cada individuo domina a una cantidad distinta de individuos), 
el peor caso para esta función tiene complejidad $O(N^2)$. 
%La complejidad completa del algoritmo es entonces $O(mN^2) + O(N^2)$ lo que 
%es equivalente a $O(N^2)$.

\subsubsection{Función \it{crowding-distance-assignment}}

La función {\it crowding-distance-assignment} tiene el cometido de asignar a cada solución un valor de distancia a la solución más cercana dentro del $F_i$ al que pertenece, con el  objetivo de que en la consolidación de las soluciones se tome en cuenta el factor diversidad.

Para tener un estimado de la densidad de soluciones, en la cercanía de un punto particular de la población se toma la distancia
promedio de los dos puntos mas cercanos a él para cada uno de los criterios de optimización. Este valor, denominado $i_{distance}$ 
sirve como un estimado del tamaño del hipercubo que contiene al individuo $i$ sin incluir a ningún otro punto en la población.
 Para el calculo de $i_{distance}$, NSGA-II utiliza el algoritmo \ref{nsgaII::crowding-distance-assignment},
donde $L[i].m$ se refiere al valor del objetivo $m$ para el individuo $i$ del conjunto $L$, y la función $sort(L,m)$ ordena
el conjunto de soluciones $L$ de acuerdo al valor del objetivo $m$. 

\begin{algorithm}
\footnotesize
\caption{{\it crowding-distance-assignment}}
\label{nsgaII::crowding-distance-assignment}
\begin{algorithmic}
\STATE$l = |L|$
\FORALL{$i \in L$}
\FORALL{$m$}
\STATE $L = sort(L,m)$
\STATE $L[1]_{distance} = L[l]_{distance} = \infty$
\FOR{$i = 2$ $to$ $(l - 1)$}
\STATE $L[i]_{distance} = L[i]_{distance} + (L[i + 1].m - L[i-1].m)$
\ENDFOR
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\footnotesize
\caption{bucle principal de NSGA-II}\label{nsgaII::main-loop}
\begin{algorithmic}
\STATE$R_t = P_t \cup Q_t$
\STATE$F = ${\it fast-nondominated-sort}$(R_t)$
\REPEAT
\STATE {\it crowding-distance-assignment}$(F_i)$
\STATE $P_{t+1} = P_{t+1} \cup F_i$ 
\STATE $i = i + 1$
\UNTIL{$|P_{t+1}| < N$}
\STATE $sort(P_{t+1}, {\geq}_n)$
\STATE $P_{t+1} =  head(P_{t+1}, N)$
\STATE $Q_{t+1} = ${\it make-new-pop}$(P_{t+1})$
\STATE $t = t + 1$
\end{algorithmic}
\end{algorithm}

En el algoritmo \ref{nsgaII::main-loop} se puede observar la integración de las funciones {\it non-domina\-ted-sort} y {\it crowding-distance-assignment} al bucle principal de NSGA-II. En el algoritmo \ref{nsgaII::main-loop}, $t$ representa el 
número de generación actual, $P_t$ es el conjunto de padres de la generación actual y $R_t$ es el conjunto de hijos. La función
{\it fast-nondominated-sort} se aplica a la unión de padres e hijos. Luego, por cada $F_i$ se
aplica la asignación de distancias de {\it crowding}, y se lo agrega completamente al conjunto de padres en orden creciente. Cuando el conjunto de padres
está completo, se ordena según la relación ${\geq}_n$ definida en \ref{nsgaII::crazy-sort-operator}, que utiliza el operador {\it rank} y la distancia de
forma de ordenar la población para dejar en último lugar a las soluciones que se encuentren en una región del espacio muy representada.
Luego se toman los primeros $N$ individuos para construir $P_{t+1}$, en base a ellos y mediante los operadores evolutivos
se obtiene $Q_{t+1}$, culminando la generación.

\begin{equation}
\footnotesize
\label{nsgaII::crazy-sort-operator}
i {\geq}_n j \Leftrightarrow (i_{rank} < j_{rank}) \vee ((i_{rank} = j_{rank}) \wedge (i_{distance} > j_{distance}))
\end{equation}

En la clase {\tt NSGAII} se encuentran implementaciones de las funciones {\it fast-nondominated-sort} y
 {\it crowding-distance-assignment}. El bucle principal del MOEA que 
representa a NSGA-II se corresponde directamente con el descrito en el algoritmo \ref{nsgaII::main-loop} y se puede apreciar
en la documentación técnica de MOE.


\section{Resumen}
Se presentó en este capítulo la consolidación de la investigación realizada en MOEAs paralelos en la forma de un entorno
de trabajo que permite el uso e investigación de los MOEA como solución a MOP. Se establecieron los objetivos del {\it framework},
se hizo un repaso por su diseño e implementación, y además se detalló la implementación de NSGA-II en el contexto de MOE. En el capítulo
siguiente se muestran los resultados de la puesta en práctica del {\it framework} sobre un caso de prueba que contempla los problemas ZDT \cite{ZDT_2000}. Las ejecuciones de prueba se realizaron utilizando los problemas ZDT vistos en la sección \ref{standard-problems} para comprobar 
la validez de la implementación y además obtener métricas de las ejecuciones que permitan comparar MOE con otros {\it frameworks}.

\chapter{Evaluación experimental}\label{chapter::results}

Este capítulo describe los experimentos realizados para comprobar el comportamiento del {\it framework} MOE 
y la validez de la implementación de NSGA-II provista.  
Con ese fin se realizaron pruebas para analizar la calidad de los resultados al resolver los problemas ZDT
 \cite{ZDT_2000}, analizando las métricas: cantidad de puntos no dominados, distancia generacional, {\it spread} 
y {\it spacing}. También se realizaron pruebas para medir la evolución del {\it speedup} de la versión paralela utilizando distintas cantidades de islas. 
Los experimentos se realizaron en una red de computadores idénticos con la siguiente configuración por nodo:


\begin{description}
\item[Sistema Operativo] GNU/Linux, Fedora Core 6 con kernel 2.6.18 compilado para 64 bits
\item[Procesador] Intel Pentium D @2.80GHz (dual core)
\item[Memoria] 1GB
\item[Red] Ethernet 10/100 Mb switcheada
\item[MPICH] versión 1.27p1
\end{description}



En los experimentos se utilizaron los valores parámetros para el NSGA-II  son los recomendados en las referencias \cite{Coello_Coello_MOEA, Deb_2000, Nesmachnow_2004}
y en la implementación del algoritmo hecha por el Deb. Los valores de los parámetros se presentan en la tabla \ref{table::parameters}.

\begin{table}
\begin{tabular}{|l|l|}
\hline
    Parámetro & Valor \\
\hline
\hline
    Tamaño de la población & 400 \\
\hline
    Cantidad de generaciones & 500 \\
\hline
    Operador de cruce & {\it SBX} para codificación real \\ & y {\it DPX} para binaria\\
\hline
    Probabilidad de cruce & 0.9 \\
\hline
    Operador de mutación & {\it Polinomial} para real \\ & y Mutación simple para binaria \\
\hline
    Probabilidad de mutación & $1/L$ siendo $L$ el número de variables \\ & involucradas,  o $1/N$ con $N$ el tamaño del \\ & {\it string} de bits, en caso de codificación  \\ & binaria \\
\hline
    Migración & Sincrónica cada 25 generaciones \\ & migrando 4 individuos por vez \\
\hline
    Topología de las islas & Anillo unidireccional \\
\hline
    Cantidad de interacciones finales  & 20 \\
    
\hline
    
\end{tabular}
\caption{Parámetros de ejecución}\label{table::parameters}
\end{table}

\section{Métricas de calidad de soluciones}\label{section::quality_experiments}

Los experimentos realizados con el objetivo de comparar la calidad de los resultados de la versión serial y la paralela, 
 utilizando dos escenarios: uno serial y el otro paralelo utilizando cuatro islas, distribuidas en forma de anillo unidireccional.

Se hicieron cincuenta ejecuciones independientes para cada problema en modos serial y paralelo. Como se puede apreciar en la tabla \ref{table::parameters}, se utilizaron valores altos para el tamaño de población 
y cantidad de generaciones, de forma de exigir alto poder de cómputo y apreciar de mejor manera las virtudes del paralelismo, dada la relativa sencillez de los problemas.  

Los valores que se muestran en la tabla \ref{table::metrics} se corresponden
con el promedio de los valores de las métricas indicadas y las desviaciones estándar de los promedios ($\sigma$ en la tabla). 
En la tabla \ref{table::metrics}, {\it ND} se refiere a la cantidad de puntos no dominados y {\it GD} a la distancia generacional. 

Para el caso particular de {\it ZDT5} se omiten los valores de {\it spread} y {\it spacing}, porque el frente consiste en 
31 puntos discretos y estas métricas se refieren a la distribución de puntos a lo largo de un frente contínuo, por lo que carece de sentido aplicarlas al caso particular de {\it ZDT5}.


\begin{table}[h]
\begin{tabular}{|l|r|r|r|r|}
\hline
                & {\it ND}     & {\it GD} & {\it Spacing} & {\it Spread} \\
\hline
\hline
    ZDT1 serial & $396.960000$ & $0.000070$  & $0.075293$      & $0.002667$ \\
    $\sigma$    & $1.760798$   & $0.000006$  & $0.000716$      & $0.000973$ \\
\hline
    ZDT1 paralelo & $396.560000$ & $0.000072$  & $0.075261$      & $0.002736$ \\
    $\sigma$      & $2.177435$   & $0.000010$  & $0.000925$      & $0.001029$ \\
\hline
    ZDT2 serial & $396.740000$ & $0.000026$  & $0.075165$      & $0.002279$ \\
    $\sigma$    & $1.700060$   & $0.000001$  & $0.000836$      & $0.001247$ \\
\hline
    ZDT2 paralelo & $396.760000$ & $0.000025$  & $0.075080$      & $0.002778$ \\
    $\sigma$      & $1.779245$   & $0.000001$  & $0.000869$      & $0.001579$ \\
\hline
    ZDT3 serial & $398.220000$ & $0.000162$  & $0.317193$      & $0.100220$ \\
    $\sigma$    & $1.217056$   & $0.000003$  & $0.003944$      & $0.001972$ \\
\hline
    ZDT3 paralelo & $398.500000$ & $0.000162$  & $0.317578$      & $0.100305$ \\
    $\sigma$      & $1.164965$   & $0.000010$  & $0.004274$      & $0.001692$ \\
\hline
    ZDT4 serial & $393.720000$ & $0.000070$  & $0.074771$      & $0.003049$ \\
    $\sigma$    & $2.339021$   & $0.000004$  & $0.000765$      & $0.001112$ \\
\hline
    ZDT4 paralelo & $394.540000$ & $0.000070$  & $0.074982$      & $0.003008$ \\
    $\sigma$      & $2.072266$   & $0.000005$  & $0.000700$      & $0.001054$ \\
\hline
    ZDT5 serial & $53.760000$   & $0.022580$  & $$      & $$ \\
    $\sigma$    & $1.767738$   & $0.021282$  & $$      & $$ \\
\hline
    ZDT5 paralelo & $55.600000$ & $0.007117$  & $$      & $$ \\
    $\sigma$      & $10.561772$ & $0.012770$  & $$      & $$ \\
\hline
    ZDT6 serial & $330.740000$ & $0.000160$  & $0.077742$      & $0.003574$ \\
    $\sigma$    & $6.384963$   & $0.000005$  & $0.000858$      & $0.000766$ \\
\hline
    ZDT6 paralelo & $338.640000$ & $0.000161$  & $0.077312$      & $0.003507$ \\
    $\sigma$      & $5.920425$   & $0.000004$  & $0.001166$      & $0.000936$ \\
\hline
\end{tabular}
\caption{Resultados de los experimentos}\label{table::metrics}
\end{table}

Dado que uno de los objetivos fundamentales de MOE es proveer un {\it framework} para la utilización de MOEAs paralelos se presentan en la siguiente sección los
experimentos realizados para medir su capacidad de aprovechar el poder de cómputo de una red de computadores.
\clearpage

\section{Desempeño Computacional}\label{section::moe_computing_experiments}

Para medir el desempeño computacional de MOE se utilizaron los problemas ZDT para comparar los tiempos de ejecución de
la versión serial y paralela en dos escenarios. En el primer escenario (en adelante escenario A) se utilizaron exactamente los mismos parámetros que los usados en las medidas de calidad de soluciones. En el segundo escenario (en adelante escenario B) se
incrementa la cantidad de generaciones de 500 a 1500 de forma de poder apreciar como afecta al {\it speedup} un incremento
en la complejidad del problema. En el modo paralelo para ambos escenarios se utilizaron desde dos hasta nueve islas con el
objetivo de analizar la evolución del valor de {\it speedup} en los experimentos respecto a la cantidad de procesadores utilizados, en relación al {\it speedup} lineal.

En las tablas \ref{table::speedup_1_3_500} y \ref{table::speedup_4_6_500} se presentan los tiempos de ejecución (en milisegundos) para el 
escenario A y en las tablas \ref{table::speedup_1_3_1500} y \ref{table::speedup_4_6_1500} los tiempos de ejecución para el escenario B. Se incluyen
además los valores de {\it speedup} para cada experimento y los promedios de {\it speedup} y tiempos de ejecución.

\clearpage 

\begin{table}[h]
\begin{tabular}{|l|r|r|r|}

\hline
                & {ZDT1}         & {ZDT2}         & {ZDT3}         \\
\hline
\hline
    serial      & $20205.740000$ & $20371.480000$ & $20343.180000$ \\
    $\sigma$    & $117.957068$   & $62.552587$    & $83.704458$    \\
\hline
    2 nodos     & $7923.280000$  & $7910.920000$  & $8060.280000$ \\
    $\sigma$    & $325.974523$   & $290.726524 $  & $324.051775 $ \\
 {\it speedup}  & $2.550173$     & $2.575108$   & $2.523880$ \\
\hline

    3 nodos     & $5602.440000$  & $6378.520000$  & $6853.571429$ \\
    $\sigma$    & $374.600585$   & $715.147116$   & $870.139500 $ \\
 {\it speedup}  & $3.606596$     & $3.193762$     & $2.968259$ \\

\hline

    4 nodos     & $5022.980000 $ & $5199.020000$  & $5192.500000 $ \\
    $\sigma$    & $347.234467$   & $518.063249 $  & $564.873555$ \\
 {\it speedup}  & $4.018823$     & $ 4.022659$    & $3.917800$ \\

\hline

    5 nodos     & $4913.700000 $ & $4980.540000$  & $4983.700000$ \\
    $\sigma$    & $192.718919 $  & $315.254948$   & $257.707337 $ \\
 {\it speedup}  & $4.112123$     & $4.090215$     & $ 4.081943$ \\

\hline

    6 nodos     & $5288.560000$ & $5344.400000$  & $5408.860000$ \\
    $\sigma$    & $316.413586$  & $344.926138$   & $569.575460 $ \\
 {\it speedup}  & $3.820650$     & $ 3.811743$     & $ 3.761084$ \\


\hline

    7 nodos     & $5527.060000$ & $5717.240000$  & $5602.420000$ \\
    $\sigma$    & $288.548331$  & $408.267097 $   & $308.216071 $ \\
 {\it speedup}  & $3.655784$     & $3.563166$     & $ 3.631141$ \\

\hline

    8 nodos     & $6109.040000 $ & $6149.280000 $  & $ 6157.500000$ \\
    $\sigma$    & $870.159637 $  & $491.080111 $   & $446.753973$ \\
 {\it speedup}  & $3.307514$     & $3.312823$     & $3.303805$ \\

\hline

    9 nodos     & $6750.220000 $ & $6811.580000 $  & $7125.660000 $ \\
    $\sigma$    & $666.369000 $  & $733.258233 $   & $1075.466726$ \\
 {\it speedup}  & $2.993345$     & $2.990712$     & $2.854918$ \\

\hline

\end{tabular}
\caption{Tiempos de ejecución en el escenario A para: ZDT1, ZDT2 y ZDT3.}\label{table::speedup_1_3_500}
\end{table}



\begin{table}[h]
\begin{tabular}{|l|r|r|r|r|}

\hline
                & {ZDT4}         & {ZDT5}         & {ZDT6}           &{promedio}  \\
\hline
\hline
    serial      & $22043.800000$ & $20963.160000$ & $21336.980000$   & $20877.390000$\\
    $\sigma$    & $52.669939 $   & $329.721302$    & $74.671660$     & \\
\hline

    2 nodos     & $8072.960000 $ & $7381.620000 $  & $7793.960000$ & $7857.170000$\\
    $\sigma$    & $266.434888 $  & $365.979418 $   & $344.714372$  & \\
 {\it speedup}  & $ 2.730572$     & $ 2.839913$     & $2.737630$   & $2.659546$\\
\hline

    3 nodos     & $6664.320000$ & $5405.980000 $  & $5309.260000$  & $6035.681904$\\
    $\sigma$    & $625.870901$  & $618.006224 $   & $195.736475$   &\\
 {\it speedup}  & $3.307734$     & $3.877772$     & $4.0188237$    & $3.495491$\\

\hline

    4 nodos     & $4778.200000$ & $4421.980000 $  & $4687.520000$  & $4883.700000$\\
    $\sigma$    & $161.507819$  & $173.767437 $   & $145.374146 $  &\\
 {\it speedup}  & $4.613410$     & $4.740672$     & $ 4.551869$    & $4.310872$\\

\hline

    5 nodos     & $4873.700000$ & $4590.600000$  & $4794.540000$   & $4856.130000$\\
    $\sigma$    & $290.223436 $  & $268.711969$   & $194.682600$   &\\
 {\it speedup}  & $4.523011$     & $ 4.566540$     & $4.450266$    & $4.304016$\\


\hline

    6 nodos     & $5260.500000 $ & $4876.100000 $  & $5160.320000$ & $5223.123333$\\
    $\sigma$    & $825.574339$  & $349.835194 $   & $448.390657$   &\\
 {\it speedup}  & $4.190438$     & $4.299165$     & $ 4.134817$    & $4.002983$\\



\hline

    7 nodos     & $5631.920000$ & $5269.800000$  & $5548.440000$   & $5549.480000$\\
    $\sigma$    & $1203.073985$  & $342.179151$   & $401.867486 $  &\\
 {\it speedup}  & $ 3.914082$     & $3.977980$     & $ 3.845581$   & $3.764622$\\

\hline

    8 nodos     & $6484.540000$ & $ 6235.740000 $  & $6129.560000$ & $6210.943333$\\
    $\sigma$    & $1218.659890$  & $1113.704753 $  & $ 674.786048$ &\\
 {\it speedup}  & $ 3.399439$     & $3.361775$     & $ 3.480997$   & $3.361059$\\

\hline

    9 nodos     & $7194.840000 $ & $6630.240000$  & $6960.300000$  & $6912.140000$\\
    $\sigma$    & $1416.830947 $  & $892.805406 $ & $836.730890 $  &\\
 {\it speedup}  & $ 3.063834$     & $ 3.161749$   & $ 3.065525$    & $3.021681$\\

%\hline
%
%    2 nodos     & $$ & $$  & $$ \\
%    $\sigma$    & $$  & $$   & $$ \\
% {\it speedup}  & $$     & $$     & $$ \\

\hline

\end{tabular}
\caption{Tiempos de ejecución en el escenario A para: ZDT4, ZDT5 y ZDT6}\label{table::speedup_4_6_500}
\end{table}



\begin{table}[h]
\begin{tabular}{|l|r|r|r|}
\hline
                & {ZDT1}         & {ZDT2}         & {ZDT3}      \\
\hline
\hline
    serial     & $60417.320000$ & $60801.860000$  & $61044.620000$ \\
    $\sigma$    & $168.617238$  & $243.049337$   & $191.723322$ \\
 
\hline
    2 nodos     & $19830.760000$ & $19934.540000$  & $19959.460000$ \\
    $\sigma$    & $202.089853$  & $160.181811$   & $115.910981$ \\
 {\it speedup}  & $3.046646$     & $3.050075$     & $3.058430$ \\

\hline
    3 nodos     & $11811.140000$ & $11653.340000$  & $11610.560000$ \\
    $\sigma$    & $503.647310$  & $165.738743$   & $77.750821$ \\
 {\it speedup}  & $5.115282$     & $5.217547$     & $5.257680$ \\

\hline
    4 nodos     & $8878.860000$ & $8884.860000$  & $8874.080000$ \\
    $\sigma$    & $156.302038$  & $180.680913$   & $104.309164$ \\
 {\it speedup}  & $6.804625$     & $6.843310$     & $6.878980$ \\

\hline
    5 nodos     & $7914.120000$ & $7960.260000$  & $7891.540000$ \\
    $\sigma$    & $318.892448$  & $262.925365$   & $270.361225$ \\
 {\it speedup}  & $7.634117$    & $7.638175$     & $7.735450$ \\

\hline
    6 nodos     & $7530.360000$ & $7434.280000 $  & $7829.220000$ \\
    $\sigma$    & $810.343509$  & $200.730202$   & $1039.363842$ \\
 {\it speedup}  & $8.023164$     & $8.178580$     & $7.797024 $ \\

\hline
    7 nodos     & $7389.540000$ & $7341.780000$  & $7385.280000$ \\
    $\sigma$    & $294.839300$  & $206.237162$   & $227.721907$ \\
 {\it speedup}  & $8.176059$     & $8.281623$     & $8.265715$ \\

\hline
    8 nodos     & $7460.160000$ & $7360.600000$  & $7407.980000$ \\
    $\sigma$    & $709.790609$  & $159.641435$   & $251.697947$ \\
 {\it speedup}  & $8.098662$     & $8.260448$     & $8.240386$ \\

\hline
    9 nodos     & $7745.740000$ & $7711.680000$  & $8981.920000$ \\
    $\sigma$    & $239.626990$  & $350.154336$   & $1347.902132$ \\
 {\it speedup}  & $7.800070$    & $7.884385$    & $6.796388$ \\



%    2 nodos     & $$ & $$  & $$ \\
%    $\sigma$    & $$  & $$   & $$ \\
% {\it speedup}  & $$     & $$     & $$ \\
\hline

\end{tabular}
\caption{Tiempos de ejecución en el escenario B para: ZDT1, ZDT2 y ZDT3.}\label{table::speedup_1_3_1500}
\end{table}



\begin{table}[h]
\begin{tabular}{|l|r|r|r|r|}

\hline
                & {ZDT4}         & {ZDT5}         & {ZDT6}           &{promedio}  \\
\hline
\hline
    serial      & $65756.960000$ & $64032.980000$ & $63088.140000$   &   $62523.646666$\\
    $\sigma$    & $144.821771$   & $309.196225$    & $532.792949$     & \\
\hline

    2 nodos       & $19844.920000$ & $18326.980000$ & $19166.660000$   &  $19510.553333$\\
    $\sigma$      & $145.538387$   & $172.227838$    & $71.301776$     & \\
    {\it speedup} & $3.313541$   & $3.493918$    & $3.291556$   &  $ 3.209027$\\
\hline

    3 nodos       & $11286.540000$ & $9992.260000$ & $10789.620000$   &   $11190.576666$\\
    $\sigma$      & $134.403324$   & $150.995852$    & $119.255666$     & \\
    {\it speedup} & $5.826139$   & $6.408257$    & $ 5.847114$   &  $5.612003$\\
\hline

    4 nodos       & $8422.920000$ & $7460.000000$ & $8254.080000$   &    $8462.466666$\\
    $\sigma$      & $168.832708$   & $232.071593$    & $407.514759$     & \\
    {\it speedup} & $7.806907$   & $8.583509$    & $7.643267$   &  $7.426766$\\
\hline

    5 nodos       & $7457.860000$ & $6608.240000$ & $7011.120000$   &  $7473.856666$\\
    $\sigma$      & $332.130722$   & $214.325764$    & $168.483226$     & \\
    {\it speedup} & $8.817135 $   & $9.689869$    & $8.998296$   &  $8.418840$\\
\hline

    6 nodos       & $7016.460000$ & $6431.160000$ & $6701.380000$   &  $7157.143333$\\
    $\sigma$      & $160.917676$   & $228.804645$    & $185.828634$     & \\
    {\it speedup} & $9.371814 $   & $9.956676$    & $9.414201$   &  $8.790243$\\
\hline

    7 nodos       & $7035.400000$ & $6681.300000$ & $6835.740000$   &  $7111.506666$\\
    $\sigma$      & $318.005712$   & $364.991208$    & $763.542598$     & \\
    {\it speedup} & $9.346584 $   & $9.583910$    & $9.229160$   &  $8.813841$\\

\hline

    8 nodos       & $7181.360000$ & $6621.180000 $ & $6743.900000$   &  $7129.196666$\\
    $\sigma$      & $719.184679$   & $482.976980$    & $165.101855$     & \\
    {\it speedup} & $9.156616$   & $9.670931$    & $9.354845$   &  $8.796981$\\
\hline

    9 nodos       & $7647.800000 $ & $7343.660000$ & $7485.960000$   &  $7819.460000$\\
    $\sigma$      & $395.620824$   & $467.101685$    & $663.798499$     & \\
    {\it speedup} & $8.598153$   & $8.719491$    & $8.427528$   &  $8.037669$\\
\hline

%    2 nodos       & $$ & $$ & $$   & \\
%    $\sigma$      & $$   & $$    & $$     & \\
%    {\it speedup} & $$   & $$    & $$   &  $$\\
%\hline

\end{tabular}
\caption{Tiempos de ejecución en el escenario B para: ZDT4, ZDT5 y ZDT6.}\label{table::speedup_4_6_1500}
\end{table}

\clearpage


\begin{figure}[h]
\centering
\includegraphics[scale=0.65]{graphs/tiempos_promedio.png}
\caption{Evolución del tiempo de ejecución promedio.}\label{fig:execution_evolution}
\end{figure}


\begin{figure}[h]
\centering
\includegraphics[scale=0.65]{graphs/speedup_promedio.png}
\caption{Evolución del {\it speedup} promedio.}\label{fig:speedup_evolution}
\end{figure}


En la figura \ref{fig:execution_evolution} se presenta la evolución del promedio del tiempo de ejecución de los problemas ZDT. 
Se puede apreciar la disminución abrupta de los tiempos de ejecución al paralelizar sobre dos y tres procesadores, esta tendencia a la baja disminuye a medida que se aumentan los procesadores utilizados, hasta que al finalmente aumenta el tiempo de
ejecución. Teóricamente la mejora en el rendimiento por la incorporación de islas aumenta hasta que la complejidad
de las comunicaciones necesarias para la sincronización de los procesos sea lo suficientemente grande como para pesar
en el tiempo de ejecución total. En el escenario A el umbral se alcanza cuando se utilizan cuatro procesadores, mientras que 
en el escenario B cuando se utilizan siete procesadores. La diferencia responde a que en el escenario B la complejidad de los
problemas es mayor. 

En la figura \ref{fig:speedup_evolution} se muestra la evolución del {\it speedup} a lo largo de los experimentos, apreciándose
{\it speedups} superlineales para ambos escenarios. En el caso del escenario A existe superlinealidad en el {\it speedup} hasta que se incorporan cuatro procesadores y en el caso del escenario B hasta que se incorporan ocho procesadores, coincidiendo con las observaciones realizadas sobre la evolución del tiempo de ejecución.

Es importante notar para el escenario B, que a pesar del aumento en los tiempos de ejecución para ocho procesadores el rendimiento es superlineal. Este
efecto se debe a que la superlinealidad que presenta el uso de siete procesadores en el escenario B es bastante alta, y el aumento en los tiempos de ejecución
por el uso de ocho procesadores es pequeña, por lo que se obtienen valores de {\it speedup} similares. 


\section{Conclusiones}

A continuación se presentan las conclusiones extraídas de los resultados de los experimentos expuestos en las secciones anteriores.

%Los resultados presentados en las secciones anteriores permiten extraer conclusiones sobre la validez funcional de MOE, sobre la calidad de los resultados obtenidos y sobre la eficiencia comptuacional que se observa en los experimentos.

\subsection{Validez de la implementación}

Los resultados obtenidos muestran que se resolvieron satisfactoriamente los problemas ZDT. Los problemas ZDT presentados en la seccion \ref{standard-problems} es un conjunto de problemas que plantean dificultades al ser resueltos utilizando MOEAs, el hecho de que en los experimentos se hayan resuelto satisfactoriamente implica que la implementación es correcta desde el punto de vista funcional. 

Las pruebas realizadas para evaluar el desempeño computacional en la seccion \ref{section::moe_computing_experiments} muestran que existe una mejora considerable en el rendimiento computacional cuando se comienzan a agregar procesadores, esa mejora se reduce en la medida que se sigan agregando procesadores al sistema. Observando los resultados se concluye que MOE tiene los elementos necesarios para brindar el soporte adecuado a la construcción de soluciones paralelas para MOPs utilizando MOEAs.

\subsection{Calidad de los resultados}

Los resultados de las pruebas realizadas para medir los valores de las métricas: distancia generacional, cantidad de puntos no dominados, {\it spread} y {\it spacing} presentados en la tabla \ref{table::metrics}, muestran que los resultados obtenidos en la versión serial son similares a los obtenidos utilizando la versión paralela. Lo que demuestra que MOE no afecta el correcto funcionamiento del MOEA utilizado al ejecutarse en modo paralelo.

Los valores de los parámetros para NSGA-II utilizados en las ejecuciones cuyos resultados se presentan en la sección \ref{section::quality_experiments} (tabla \ref{table::parameters}) son idénticos a los utilizados en las evaluaciones de PNSGAII \cite{Nesmachnow_2004}, lo que habilita una comparación de los resultados obtenidos por ambos proyectos. 
Los resultados obtenidos por PNSGAII son de características similares a los obtenidos por MOE, aunque
existen algunas diferencias. Los resultados de Nesmachnow son mejores que los de la tabla \ref{table::metrics} respecto a la distancia generacional, de un orden de magnitud en algunos los casos. Sin embargo, en los resultados de cantidad de puntos no dominados, {\it spread} y {\it spacing} los resultados de la tabla \ref{table::metrics} son mejores que los de PNSGAII en casi todos los problemas ZDT.
Dadas estas diferencias y el hecho que la implementación de PNSGAII está basada directamente en la implementación de referencia de Deb \cite{Deb_2000}, es
 válido concluir que la implementación de NSGA-II en MOE tiene diferencias con la implementación de referencia, que amerita un análisis más profundo que se propone como trabajo futuro.


\subsection{Eficiencia Computacional}

Los resultados muestran que MOE obtiene valores de {\it speedup} altos para los problemas ZDT. Para confirmar este comportamiento, 
es necesario llevar a cabo experimentos con problemas
reales y comparar los tiempos de ejecución con otros proyectos para determinar si los rendimientos son competitivos. 
Esta tarea se ha planteado como trabajo futuro.

%En la tabla \ref{table::times} se encuentran los resultados de los experimentos tomando en cuenta el tiempo de ejecución,
%todos los resultados son en milisegundos, y se corresponden con el promedio del tiempo de ejecución real de las cincuenta ejecuciones.

%Entonces podemos apreciar la mejora sustantiva en el rendimiento de las aplicaciones, en recursos computacionales por el uso
%del paralelismo, sin por ello perder calidad en los resultados. La notoria superlinealidad de los valores de {\it speedup} nos indican
%que se hace un correcto uso del paralelismo, no solamente por parte del algoritmo utilizado sino también por el entorno que
%lo contiene. 

%Además observando la implementación en si del algoritmo, es una traducción casi directa del artículo \cite{Deb_2000}
%que lo define, ésto junto con los resultados obtenidos hacen pensar que este {\it framework} puede tener una gran utilidad 
%futura, para las personas interesadas en los {\it MOEA}.


\chapter{Conclusiones y trabajo futuro}\label{chapter::final}

Desde el punto de vista de la consolidación del conocimiento en el área de MOEAs paralelos el proyecto presenta las bases
de los MOPs, MOEAs y paralelismo. Se presentan los elementos fundamentales del área tanto desde el punto de vista teórico 
como desde el punto de vista práctico. Se argumenta sobre la capacidad de los EA como método robusto y flexible para la resolución
de problemas de optimización, en particular de los MOPs. Además se presenta al paralelismo como técnica para incrementar el rendimiento
de las aplicaciones, particularmente aplicada a los EA. Todos los conocimientos adquiridos en la fase de investigación se vuelcan
en la implementación de MOE, como propuesta de {\it framework} para aplicar MOEAs en el ámbito académico como en el práctico.

La implementación de MOE brinda una interfaz sencilla para la composición de soluciones a MOPs utilizando MOEAs, que son 
ejecutables en ambientes seriales y paralelos. El conjunto de paquetes y clases que componen a MOE son modulares y poco acoplados lo que permite
que el {\it framework} esté preparado para el cambio. Los resultados demuestran un 
correcto uso de los ciclos de CPU y memoria, lo que hace factible la construcción de soluciones a problemas reales utilizando MOE.

Se realizaron evaluaciones de calidad de soluciones y de rendimiento sobre la implementación de NSGA-II del {\it framework} utilizando
los problemas ZDT \cite{ZDT_2000} en ambientes seriales y paralelos. Para la evaluación del rendimiento se utilizaron hasta nueve
procesos independientes. Los resultados obtenidos permiten afirmar que la calidad de soluciones son aceptables en relación a las obtenidas en
idénticos escenarios utilizando PNSGAII \cite{Nesmachnow_2004}. La evaluación del rendimiento en tiempo de ejecución del {\it framework} utilizando
distinta cantidad de procesadores permitió observar la evolución del {\it speedup}, este análisis muestra {\it speedups} superlineales a pesar 
de la sencillez de los problemas.

Como herramienta, el {\it framework} es un trabajo continuo, y flexible pudiéndose extender mediante el agregado de problemas, algoritmos,
 codificaciones y operadores. En particular es deseable contar con otros MOEAs de la segunda generación y un análisis de la fidelidad de la implementación
de operadores de cruce, selección y mutación utilizados, en relación a las implementaciones de referencia correspondientes.

Debido a su modularidad, MOE es útil como punto de partida para extensiones mas allá de los MOEA. Desde este punto de vista, sería interesante la incorporación de otras
  técnicas de computación evolutiva: GA, ES y EP; así como otras metaheurísiticas basadas en conjuntos de soluciones tentativas como {\it Simulated Annealing}. 

Sería interesante también ensayar otros modelos de paralelismo, incorporándolos para ponerlos a disposición. Una manera sencilla
de avanzar en esta área podría ser incluir un mejor soporte para el modelo celular y el modelo de grano grueso. En un nivel 
de sofisticación superior se podrían ensayar modelos de paralelismo híbridos, que permitan aprovechar mejor los multiprocesadores.

En otra línea de trabajo sobre el paralelismo se podrían ensayar técnicas similares a las que Jaimes y Coello propusieron en su trabajo de 2005 \cite{Lopez05a}, basadas
en la idea de tener evoluciones heterogéneas en las islas o vecindarios. Las variaciones evolutivas podrían incluir el uso de distintos operadores
evolutivos, codificaciones, etc. 

Para mantener actualizado al sistema se hace necesaria la migración de {\tt NetStream} a alguna implementación de {\it MPI 2.0}. 
Complementariamente, es necesario realizar un análisis exhaustivo de la implementación de NSGA-II para subsanar las diferencias
con la implementación de referencia expuestas en el capítulo anterior, tratando de contar con una implementación lo mas fiel posible 
a la descripción original del algoritmo.


\bibliographystyle{plain}
\bibliography{references}
\end{document}
